c语言结构体实现线性表的存储,线性表的存储方式及其操作（C语言版）

该篇也是复习数据结构总结的 ，虽然很简单 但方便以后使用。

线性表的顺序存储

1.定义一个结构体，因为在高级语言中  数组具有随机存储的特性，所以通常用数组来表示顺序存储。

typedef struct LNode *List;structLNode{

ElementType Data[maxsize];int last; //线性表的长度为 last+1

};struct LNode L; //定义了一个结构体

List PtrL; //定义了一个结构体指针 访问下标 i的元素为 L.Data[i] 或者为 Ptr-> Data[i]

2.初始化操作

List MakeEmpty()

{

List PtrL;

PtrL= (List)malloc(sizeof(structLNode));

PtrL->last = -1;returnPtrL;

}

3.查找操作

intFind(ElementType X,List PtrL)

{int i = 0;while(i<=PtrL->last && PtrL ->Data[i] !=X)

i++;if(i>PtrL->last) return -1;else returni;

}

4.插入操作   时间复杂度为  O(N)

void Insert(ElementType X,inti,List PtrL)

{intj;if(PtrL->last == maxsize-1)

{

printf("表满");return;

}if(i<1 || i>PtrL->last+2) /*因为插入的是第 i个位置的元素 (1<=i<=1+n)*/{

printf("位置不合法");return;

}for(j=PtrL->last;j>=i-1;j--)

PtrL->Data[j+1]=PtrL->Data[j]; /*将 ai ~an 倒序向后移动*/PtrL->Data[i-1] =X;

PtrL->last++;return;

}

5.删除操作  第i个元素   1<=i<=n

void Delete(inti,List PtrL)

{intj;if(i<1 || i>PtrL->last)

{

printf("不存在第%d个元素",i);return;

}for(j=i;j<=PtrL->last;j++)

PtrL->Data[j-1] = PtrL->Data[j];

PtrL->last--;return;

}

线性表的链式存储结构

1.结构体

typedef struct LNode *List;structLNode{

ElementType Data;

List Next;//线性表的长度为 last+1

};struct LNode L; //定义了一个结构体

List PtrL; //定义了一个结构体指针 访问下标 i的元素为 L.Data[i] 或者为 Ptr-> Data[i]

2.因为链表不像顺序表那样数组直接有表长，所以 我们加上一个求表长的操作。

intLength(List PtrL)

{

List p=PtrL;int j =0;while(p) /*p不为空*/{

p= p->Next;

j++;

}returnj;

}

3.查找第K个元素

List FindKth(intK,List PtrL)

{

List p=PtrL;while(p!=NULL && i

{

p= p->Next;

i++;

}if(i == K) return p; //找到第K个返回指针

else returnNULL;

}

3.2按值查找

List Find(ElementType X,List PtrL)

{

List p= PtrL; //临时变量设置为链表表头

while(P!=NULL && p->Data !=X)

p= p->Next;returnp;

}

4.链表的插入，  这里一定要注意操作顺序

详细请看图示

List Insert(ElementType X,inti,List PtrL)

{

List p,s;if(i == 1) //新节点在表头

{

s= (List)malloc(sizeof(struct LNode)); //申请、填装节点

s->Data =X;

s->Next =PtrL;return s; //返回表头指针

}

p= FindKth(i-1,PtrL); //查找第 i-1个节点

if(p == NULL) //第 i-1 个节点不存在，不能插入

{

printf("参数i错");returnNULL;

}else{

s= (List)malloc(sizeof(struct LNode)); //申请填装节点

s->Data =X;

s->Next = p->Next; //新节点插入在第 i - 1个节点的后面

p->Next = s; //注意里 两句的顺序不能改变 ！！！

return PtrL; //返回新的链表的头指针

}

}

5.删除操作

List Delete(int i,List PtrL) //删除第i个节点

{

List p,s;if(i == 1) //如果删除的是表的第一个节点

{

s= PtrL; //s指向第一个节点

if(PtrL != NULL) PtrL = PtrL->Next; //从链表中删除

else returnNULL;free(s);returnPtrL;

}

p= FindKth(i-1,PtrL);if(p ==NULL)

{

printf("第%d个节点不存在",i-1);returnNULL;

}else if(p->Next ==NULL)

{

printf("第%d个节点不存在",i); returnNULL;

}else{

s= p->Next; //s指向第i个节点

p->Next = s->Next; //从链表中删除

free(s); //释放被删除节点

returnPtrL;

}

}

由于刚开始学的时候书上的是C++版本，搞了半天才搞懂，而且网上查的都觉得不对劲，自己从新写了一遍提供大家和我自己参考。后续更新更多关于数据结构的内容。谢谢大家啊