c语言实现线性表的链式存储,线性表的顺序存储和链式存储c语言实现

一.线性表的顺序存储

typedef int ElemType;

typedef structList

{

ElemType*data;//动态分配 ,需要申请空间

intlength;

}List;

0.完整代码

#include #include

#define MaxSize 50

#define TRUE 1

#define FALSE 0typedefintElemType ;structList

{

ElemType*data;//动态分配 ,需要申请空间

intlength;

};void InitList(List *p);//初始化表

int ListInsert(List *p,int i,ElemType e);//插入操作 (前插),在第i个位置插入数据e

int ListDelete(List *p,int i);//删除操作，删除第i个位置数据

int ListFindValue(List L,ElemType e);//按值查找元素e ,返回e在顺序表表的位置

int ListFindLocate(List L,int i);//按位查找第i位的值

int Empty(List L); //判空，如果表为空返回TRUE

void PrintList(List L);//输出操作

intmain()

{

List L;

InitList(&L);

ListInsert(&L,1,1);

ListInsert(&L,2,3);

ListInsert(&L,3,5);

ListInsert(&L,4,7);

ListInsert(&L,5,9);

PrintList(L);return 0;

}void InitList(List *p)

{

p->data=(ElemType*)malloc(sizeof(ElemType)*MaxSize);

p->length=0;

}int ListInsert(List *p,inti,ElemType e)

{if(i<1 || i>p->length+1)

{return FALSE;//插入位置不合法

}if(p->length>=MaxSize)

{return FALSE;//顺序表已满

}for(int j=p->length;j>=i;j--)

{

p->data[j]=p->data[j-1];

}

p->data[i-1]=e;

p->length++;returnTRUE;

}int ListDelete(List *p,inti)

{if(i<1 || i>p->length)

{returnFALSE;

}for(int j=i;jlength;j++)

{

p->data[j-1]=p->data[j];

}

p->length--;returnTRUE;

}intListFindValue(List L,ElemType e)

{for(int i=0;i

{if(L.data[i]==e)

{return i+1;

}

}returnFALSE;

}int ListFindLocate(List L,inti)

{return L.data[i-1];

}voidPrintList(List L)

{for(int i=0;i

{

printf("%d",L.data[i]);

}

printf("\n");

}intEmpty(List L)

{if(L.length==0)

{returnTRUE;

}else{returnFALSE;

}

}

View Code

1.初始化顺序表

void InitList(List *p)

{

p->data=(ElemType*)malloc(sizeof(ElemType)*MaxSize);

p->length=0;

}

View Code

2.插入操作 ,在第i个位置插入数据e

int ListInsert(List *p,inti,ElemType e)

{if(i<1 || i>p->length+1)

{return FALSE;//插入位置不合法

}if(p->length>=MaxSize)

{return FALSE;//顺序表已满

}for(int j=p->length;j>=i;j--)

{

p->data[j]=p->data[j-1];

}

p->data[i-1]=e;

p->length++;returnTRUE;

}

View Code

3.删除操作，删除第i个位置数据

int ListDelete(List *p,inti)

{if(i<1 || i>p->length)

{returnFALSE;

}for(int j=i;jlength;j++)

{

p->data[j-1]=p->data[j];

}

p->length--;returnTRUE;

}

View Code

4.按值查找元素 ,返回元素在顺序表的位置

intListFindValue(List L,ElemType e)

{for(int i=0;i

{if(L.data[i]==e)

{return i+1;

}

}returnFALSE;

}

View Code

5.按位置查找元素

int ListFindLocate(List L,inti)

{return L.data[i-1];

}

View Code

6.判断顺序表是否为空，为空返回TRUE

intEmpty(List L)

{if(L.length==0)

{returnTRUE;

}else{returnFALSE;

}

}

View Code

7.显示顺序表

voidPrintList(List L)

{for(int i=0;i

{

printf("%d",L.data[i]);

}

printf("\n");

}

View Code

二.线性表的链式存储

typedef intElemType;

typedefstructNode{

ElemType data;struct Node *next;

}Node;

0.完整代码

1 #include

2 #include

3 #define TRUE 1

4 #define FALSE 0

5 typedef intElemType;6 typedef structNode{7 ElemType data;8 struct Node *next;9 }Node;10

11 Node* InitNode();//初始化创建头结点

12 Node* Node_HeadInsert(Node *L);//头插法建立链表

13 Node* Node_TailInsert(Node *L);//尾插法建立链表

14 Node* NodeInsert(Node *L,int i);//在第i个位置插入结点

15 Node* NodeDelete(Node *L,int i);//删除第i个结点

16 Node* NodeSearchNum(Node *L,int i);//按序号查找

17 Node* NodeSearchValue(Node *L,ElemType x);//按值查找

18 void PrintNode(Node *L);//显示单链表

19 Node* NodeMerge(Node *p,Node *q);//合并两个递增链表

20

21

22 intmain()23 {24 Node *L;25 L=InitNode();26 L=Node_TailInsert(L);27 L=NodeInsert(L,2);28 PrintNode(L);29 L=NodeDelete(L,1);30 PrintNode(L);31 return 0;32 }33 Node*InitNode()34 {35 Node *L;36 L=(Node*)malloc(sizeof(Node));37 L->next=NULL;38 returnL;39 }40 Node* Node_HeadInsert(Node *L)41 {42 Node *s;43 ElemType x;44 scanf("%d",&x);//插入结点的值

45 while(x!=9999)46 {47 s=(Node*)malloc(sizeof(Node));48 s->data=x;49 s->next=L->next;50 L->next=s;51 scanf("%d",&x);52 }53 returnL;54 }55

56 Node* Node_TailInsert(Node *L)57 {58 ElemType x;59 Node *s,*r=L;60 scanf("%d",&x);61 while(x!=9999)62 {63 s=(Node*)malloc(sizeof(Node));64 s->data=x;65 r->next=s;66 r=s;67 scanf("%d",&x);68 }69 r->next=NULL;70 returnL;71 }72

73 Node* NodeInsert(Node *L,inti)74 {75 ElemType x;76 Node *s,*p=NodeSearchNum(L,i-1);77 printf("输入插入节点的值:") ;78 scanf("%d",&x);79 s=(Node*)malloc(sizeof(Node));80 s->data=x;81 s->next=p->next;82 p->next=s;83 printf("插入完成!\n");84 returnL;85 }86

87 Node* NodeDelete(Node *L,inti)88 {89 Node *p,*q;90 p=NodeSearchNum(L,i-1);91 q=p->next;92 p->next=q->next;93 free(q);94 printf("删除完成!\n");95 returnL;96 }97

98 Node *NodeSearchNum(Node *L,inti)99 {100 int count=1;//计数

101 Node *p=L->next;102 if(i==0)103 returnL;104 if(i<1)105 returnNULL;106 while(p&&countnext;109 count++;110 }111 returnp;112 }113

114 Node *NodeSearchValue(Node *L,ElemType x)115 {116 Node *p=L->next;117 while(p&&p->data!=x)118 {119 p=p->next;120 }121 returnp;122 }123 void PrintNode(Node *L)124 {125 Node *p=L->next;126 printf("单链表:");127 while(p)128 {129 printf("%d",p->data);130 p=p->next;131 }132 printf("\n");133

134 }135

136 Node* NodeMerge(Node *p,Node *q)137 {138 Node *r,*t;139 r=InitNode();140 t=r;141 while(p->next&&q->next)142 {143 if(p->next->datanext->data)144 {145 t->next=p->next;146 p->next=p->next->next;147 t=t->next;148 }149 else

150 {151 t->next=q->next;152 q->next=q->next->next;153 t=t->next;154 }155 }156

157 while(p->next)158 {159 t->next=p->next;160 p->next=p->next->next;161 t=t->next;162 }163

164 while(q->next)165 {166 t->next=q->next;167 q->next=q->next->next;168 t=t->next;169 }170

171 free(p);172 free(q);173

174 returnr;175 }

View Code

1.初始化创建头结点

Node*InitNode()

{

Node*L;

L=(Node*)malloc(sizeof(Node));

L->next=NULL;returnL;

}

View Code

2.头插法建立链表

Node* Node_HeadInsert(Node *L)

{

Node*s;

ElemType x;

scanf("%d",&x);//插入结点的值

while(x!=9999)

{

s=(Node*)malloc(sizeof(Node));

s->data=x;

s->next=L->next;

L->next=s;

scanf("%d",&x);

}returnL;

}

View Code

3.尾插法建立链表

Node* Node_TailInsert(Node *L)

{

ElemType x;

Node*s,*r=L;

scanf("%d",&x);while(x!=9999)

{

s=(Node*)malloc(sizeof(Node));

s->data=x;

r->next=s;

r=s;

scanf("%d",&x);

}

r->next=NULL;returnL;

}

View Code

4.在第i个位置插入结点

Node* NodeInsert(Node *L,inti)

{

ElemType x;

Node*s,*p=NodeSearchNum(L,i-1);

printf("输入插入节点的值:") ;

scanf("%d",&x);

s=(Node*)malloc(sizeof(Node));

s->data=x;

s->next=p->next;

p->next=s;

printf("插入完成!\n");returnL;

}

View Code

5.删除第i个结点

Node* NodeDelete(Node *L,inti)

{

Node*p,*q;

p=NodeSearchNum(L,i-1);

q=p->next;

p->next=q->next;free(q);

printf("删除完成!\n");returnL;

}

View Code

6.按序号查找

Node *NodeSearchNum(Node *L,inti)

{int count=1;//计数

Node *p=L->next;if(i==0)returnL;if(i<1)returnNULL;while(p&&count

{

p=p->next;

count++;

}returnp;

}

View Code

7.按值查找

Node *NodeSearchValue(Node *L,ElemType x)

{

Node*p=L->next;while(p&&p->data!=x)

{

p=p->next;

}returnp;

}

View Code

8.显示单链表

void PrintNode(Node *L)

{

Node*p=L->next;

printf("单链表:");while(p)

{

printf("%d",p->data);

p=p->next;

}

printf("\n");

}

View Code

9.合并两个递增链表

Node* NodeMerge(Node *p,Node *q)

{

Node*r,*t;

r=InitNode();

t=r;while(p->next&&q->next)

{if(p->next->datanext->data)

{

t->next=p->next;

p->next=p->next->next;

t=t->next;

}else{

t->next=q->next;

q->next=q->next->next;

t=t->next;

}

}while(p->next)

{

t->next=p->next;

p->next=p->next->next;

t=t->next;

}while(q->next)

{

t->next=q->next;

q->next=q->next->next;

t=t->next;

}free(p);free(q);returnr;

}

View Code

输出示例：

2020-06-27

来源：oschina

链接：https://my.oschina.net/u/4386188/blog/4327064