当前位置 博文首页 > 奋斗的小跳蛙的博客：线性表的建立及操作详解 菜鸟都能看懂的教
线性表按照存储方式可以分为顺序存储和链式存储.
我们先来实现顺序表,借助一维数组来实现
定义顺序表
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#define MAXSIZE 100
typedef struct List
{
int data[MAXSIZE];
int length;
}List;
初始化顺序表
void initList(List * plist)
{
assert(plist);
memset(plist->data, 0, MAXSIZE * 4);
plist->length = 0;
}
判断顺序表是否为空
int ListEmpty(List * plist)
{
assert(plist);
//空为0,非空为-1;
if (plist->length == 0)
return 0;
else
return -1;
}
清空顺序表
void clearList(List * plist)
{
assert(plist);
plist->length = 0;
}
寻找第i个元素
int GetElem(List * plist, int i, int *e)
{
//成功为0,不成功为-1;
assert(plist);
if (i<1 || i>plist->length||plist->length == 0)
return -1;
*e = plist->data[i - 1];
return 0;
}
寻找元素e在顺序表中的位置
int LocateElem(List *plist, int e)
{
int i;
assert(plist);
for (i = 1; i <= plist->length; i++)
{
if (plist->data[i] == e)
{
return i;
}
}
return 0;
}
在第i个位置插入数据e
int ListInsert(List *plist, int i,int e)
{
int k;
//插入成功为0,失败为-1;
assert(plist);
if (plist->length == MAXSIZE)
return -1;
if (i<1 || i>plist->length + 1)
return -1;
for (k = plist->length - 1; k >= i - 1; k--)
{
plist->data[k + 1] = plist->data[k];
}
plist->data[i-1] = e;
plist->length++;
return 0;
}
删除第i个位置的元素,用e返回值
int ListDelete(List * plist, int i, int *e)
{
int k;
assert(plist);
if (i<1 || i>plist->length + 1)
return -1;
if (plist->length == 0)
return -1;
*e = plist->data[i - 1];
for (k = i - 1; k < plist->length; k++)
{
plist->data[k] = plist->data[k + 1];
}
plist->length--;
return e;
}
得到顺序表长度
int ListLength(List *plist)
{
return plist->length;
}
void print(List *plist)
{
for (int i = 0; i < plist->length; i++)
{
printf("%d ", plist->data[i]);
}
}
主函数
int main()
{
List p;
List * plist = &p;
initList(plist);
ListInsert(plist, 1, 34);
ListInsert(plist, 2, 3);
ListInsert(plist, 3, 35);
ListInsert(plist, 1, 6);
ListInsert(plist, 2, 45);
ListInsert(plist, 6, 55);
int e, k, pp;
//GetElem(plist,5, &e);
print(plist);
system("pause");
return 0;
}
链表实现
单链表的定义
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
typedef struct ListNode
{
struct ListNode * next;
int data;
}ListNode;
typedef struct Link
{
struct ListNode * head;
}Link;
初始化单链表
void initLink(Link * plist)
{
assert(plist);
plist->head = NULL;
}
销毁单链表
void ListDestroy(Link* plist)
{
assert(plist);
ListNode * tmp;
while (plist->head)
{
tmp = plist->head;
plist->head = plist->head->next;
free(tmp);
}
}
头插
void PushFront(Link * plist, int x)
{
assert(plist);
ListNode * tmp = (ListNode *)malloc(sizeof(ListNode));
tmp->data = x;
tmp->next = plist->head;
plist->head = tmp;
}
头删
void PopFront(Link *plist)
{
assert(plist);
ListNode * tmp;
if (plist->head != NULL)
{
tmp = plist->head;
plist->head = tmp->next;
free(tmp);
}
}
查找
ListNode * Listfind(Link * plist,int x)
{
assert(plist);
ListNode * tmp;
for (tmp = plist->head; tmp; tmp=tmp->next)
{
if (tmp->data == x)
{
return tmp;
}
}
return NULL;
}
第i个位置上插入x
int LinkInsert(Link* plist,int i,int x)
{
int j=1;
assert(plist);
ListNode * tmp = plist->head;
while (tmp&&j < i-1)
{
tmp = tmp->next;
j++;
}
while (!tmp || j > i)
{
return -1;
}
ListNode * cur = (ListNode*)malloc(sizeof(ListNode));
cur->data = x;
if (i == 1)
{
cur->next = plist->head;
plist->head = cur;
}
else
{
cur->next = tmp->next;
tmp->next = cur->next;
}
return 0;
}
删除第i个位置上的元素
int LinkRemove(Link*plist, int i,int *e)
{
assert(plist);
int j=1;
ListNode * tmp = plist->head;
while (tmp&&j < i - 1)
{
tmp = tmp->next;
j++;
}
if (!tmp || j > i )
{
return -1;
}
if (i == 1)
{
ListNode *y = plist->head;
*e = y->data;
plist->head = y->next;
free(y);
}
else {
ListNode * y = tmp->next;
*e = y->data;
tmp->next = tmp->next->next;
free(y);
}
return 0;
}
打印单链表
void print(Link * plist)
{
assert(plist);
ListNode * tmp;
for (tmp = plist->head; tmp; tmp = tmp->next)
{
printf("%d->", tmp->data);
}
}
主函数
int main()
{
Link L;
Link * plist = &L;
initLink(plist);
PushFront(plist, 1);
PushFront(plist, 2);
PushFront(plist, 3);
PushFront(plist, 4);
PushFront(plist, 5);
int e;
LinkInsert(plist, 1, 10);
//LinkRemove(plist,1, &e);
// printf("%d\n", e);
print(plist);
system("pause");
return 0;
}
