2.3 线性表的链式表示

知识总览

2.3.1 单链表的定义
知识总览

单链表定义

1. #include<stdio.h>
2. #include<string.h>
3. #include<stdlib.h>
4. struct LNode{
5.         int data;
6.         struct LNode *next;
7. };
8. int main(){       
9.         struct LNode *p=(struct LNode*)malloc(sizeof(struct LNode));
10.     return 0;
11. }

复制代码

typedef重命名

typedef struct LNode{
  int data;
  struct LNode *next;
}LNode,*LinkList;
等同于
struct LNode{
    int data;
    struct LNode *next;
};
typedef struct LNode LNode;
typedef struct LNode *LinkList;
 
头插法建立单链表
头插法

1. #include<stdio.h>
2. #include<string.h>
3. #include<stdlib.h>
4. typedef struct LNode{
5.   int data;
6.   struct LNode *next;
7. }LNode,*LinkList;
8. LinkList List_HeadInsert(LinkList &L){
9.         LNode *s;
10.         int x;
11.         L=(LinkList)malloc(sizeof(LNode));  //创建头节点
12.         L->next=NULL;                  //初始为空链表
13.         scanf("%d",&x);                   //输入节点的值
14.         while(x!=9999){                   //输出9999表示结束
15.                 s=(LNode*)malloc(sizeof(LNode));  //创建新节点
16.                 s->data=x;
17.                 s->next=L->next;
18.                 L->next=s;                  //将新节点插入表中，L为头指针
19.                 scanf("%d",&x);
20.         }
21.         return L;
22. }
23. int main(){
24.         LinkList L;
25.         List_HeadInsert(L);
26. }

复制代码

强调这是一个单链表      ————使用LinkList
强调这是一个节点         ————使用LNode*
 
不带头节点的单链表

1. #include<stdio.h>
2. #include<string.h>
3. #include<stdlib.h>
5. typedef struct LNode{
6.   int data;
7.   struct LNode *next;
8. }LNode,*LinkList;
9. //初始化一个空的单链表
10. bool InitList(LinkList &L){
11.         L=NULL;    //空表，//防止脏数据
12.         return true;
13. }
14. //判断单链表是否为空
15. bool Empty(LinkList L){
16.         return (L==NULL);
17. }
18. int main(){
19.         LinkList L; //声明一个指向单链表的指针 //此处并没有创建一个节点
20.         InitList(L);
21.         Empty(L);
22. }

复制代码

带头结点的单链表

1. #include<stdio.h>
2. #include<string.h>
3. #include<stdlib.h>
5. typedef struct LNode{
6.   int data;
7.   struct LNode *next;
8. }LNode,*LinkList;
9. //初始化一个单链表 (带头结点)
10. bool InitList(LinkList &L){
11.     L=(LNode*)malloc(sizeof(LNode));
12.         if(L==NULL)
13.             return false;
14.     L->next=NULL;
15.         return true;
16. }
17. //判断单链表是否为空 (带头结点)
18. bool Empty(LinkList L){
19.     if(L->next==NULL)
20.            return  true;
21.         else
22.            return false;
23. }
24. int main(){
25.         LinkList L; //声明一个指向单链表的指针
26.         InitList(L);
27.         Empty(L);
28. }

复制代码

 总结   2.3.2.1知识总览    按位序插入（带头结点）

1. #include<stdio.h>
2. #include<string.h>
3. #include<stdlib.h>
4. typedef struct LNode{
5.   int data;
6.   struct LNode *next;
7. }LNode,*LinkList;
8. //初始化一个单链表 (带头结点)
9. bool InitList(LinkList &L){
10.     L=(LNode*)malloc(sizeof(LNode));
11.         if(L==NULL)
12.             return false;
13.     L->next=NULL;
14.         return true;
15. }
16. //判断单链表是否为空 (带头结点)
17. bool Empty(LinkList L){
18.     if(L->next==NULL)
19.            return  true;
20.         else
21.            return false;
22. }
23. //在第i个位置插入元素e(带头结点)
24. bool ListInsert(LinkList &L,int i,int e){
25.         if(i<1)
26.             return false;
27.         LNode *p;  //指针p指向当前扫描到的结点
28.         int j=0;   //当前p指向的是第几个结点
29.         p=L;     //L指向头结点，头结点是第0个结点(不存数据)
30.         while(p!=NULL&&j<i-1){ //循环找到第i-1 个结点 //找位置
31.                 p=p->next;
32.                 j++;
33.         }
34.         if(p==NULL)   //i值不合法
35.            return false;
36.         LNode *s=(LNode*)malloc(sizeof(LNode));
37.         s->data=e;
38.         s->next=p->next;
39.         p->next=s;   //将结点s连到p之后
40.         return true; //插入成功
41. }
42. int main(){
43.         LinkList L; //声明一个指向单链表的指针
44.         InitList(L);
45.         Empty(L);
46.         ListInsert(L,1,9);
47. }

复制代码

        不带头节点
 
 

LNode * GetElem(LinkList L ,int i){
  int j=1;
  LNode *p=L->next;
  if(i==0)
    return L;
  if(i