单链表的各种操作

  1 #include "stdafx.h"
  2 #include <iostream>
  3 #include <exception>
  4 using namespace std;
  5 
  6 //一系列状态
  7 #define OK 1
  8 #define ERROR 0
  9 #define TRUE 1
 10 #define FALSE 0
 11 typedef int Status;
 12 
 13 //线性表的顺序存储
 14 #define MAXSIZE 20
 15 typedef int ElemType;
 16 typedef struct
 17 {
 18     ElemType data[MAXSIZE];
 19     int length;
 20 }SqList;
 21 
 22 //线性表的链式存储
 23 typedef struct Node
 24 {
 25     ElemType data;
 26     struct Node *next;
 27 }Node,*LinkList;
 28 
 29 //获取线性表元素，所以不会修改L.所以L就是一个普通参数
 30 Status GetElem(LinkList L,int i,ElemType *e)
 31 {
 32     int j;//用来向下走的
 33     LinkList p ;//命名中p一般是指指针，指向一个Node
 34     p=L->next;//L是头指针.头结点的next就是第一个结点
 35     j=1;
 36     while(p&&j<i)//p不为空或者计数器j还没有等于i时,循环继续.
 37     {
 38         p=p->next;
 39         j++;
 40     }
 41     if(!p||j>i)//对应的上面while的两个条件，个人认为这里如果i=0的时候j才会大于i
 42         return ERROR;//第i个元素不存在
 43     *e=p->data;//取出第i个元素的数据
 44     return OK;
 45 }
 46 //单链表的插入
 47 Status ListInsert(LinkList *L,int i,ElemType *e)
 48 {
 49     int j;
 50     LinkList p,s;
 51     p = *L;
 52     j = 1;//使用之前赋值
 53     while(p&&j<i)
 54     {
 55         p=p->next;
 56         ++j;
 57     }
 58     if(!p||j>i)
 59         return ERROR;
 60     s = (LinkList) malloc(sizeof(Node));//生成新的结点  分配Node大小的内存空间,并且返回了指向这块内存的指针.
 61     s->data=*e;
 62     s->next=p->next;
 63     p->next=s;
 64     return OK;
 65 
 66 }
 67 //单链表的删除
 68 Status ListDelete(LinkList *L,int i,ElemType *e)
 69 {
 70     int j;
 71     LinkList p=*L,q;
 72     j=1;
 73     while(p->next&&j<i)
 74     {
 75         p=p->next;
 76         ++j;
 77     }
 78     if(!(p->next)||j>i)
 79         return ERROR;
 80     q=p->next;
 81     p->next = q->next;
 82     *e=q->data;
 83     free(q);//让系统回收结点，释放内存.
 84     q=p;
 85     return OK;
 86 }
 87 //单链表的创建--头插法
 88 void CreateListHead(LinkList *L,int n)
 89 {
 90     LinkList p;
 91     int i ;
 92     *L =(LinkList)malloc(sizeof(Node));
 93     (*L)->next = NULL;
 94     for(i = 0;i<n;++i)
 95     {
 96         p=(LinkList)malloc(sizeof(Node));
 97         p->data=i+1;
 98         p->next = (*L)->next;
 99         (*L)->next = p;
100     }
101 }
102 
103 //单链表的创建--尾插法
104 void CreateListTail(LinkList *L,int n)
105 {
106     LinkList p,r;//r是指向尾结点的变量
107     int i ;
108     *L = (LinkList)malloc(sizeof(Node));
109     r = *L;
110     (*L)->next = NULL;
111     for(i = 0;i<n;++i)
112     {
113         p=(LinkList)malloc(sizeof(Node));
114         p->data=i+1;
115         r->next=p;
116         r=p;
117     }
118     r->next = NULL;
119 }
120 //单链表的整表删除
121 Status ClearList(LinkList *L)
122 {
123     LinkList p,q;
124     p=(*L)->next;
125     while(p)
126     {
127         q=p->next;
128         free(p);
129         p=q;
130     }
131     (*L)->next = NULL;
132     return OK;
133 }
134 //单链表的整表读取
135 Status ReadList(LinkList L)
136 {
137     LinkList p=L->next;
138     while(p)
139     {
140         cout<<(p->data)<<" ";
141         p=p->next;
142     }
143     cout<<endl;
144     return OK;
145 }
146 //获取单链表的最后一个元素
147 Status GetEndElem(LinkList L,ElemType *e)
148 {
149     LinkList p;
150     p=L->next;
151     while((p->next))
152     {
153         p=p->next;
154     }
155     *e = p->data;
156     return OK;
157 }
158 //获取链表的长度
159 Status GetListLength(LinkList L,ElemType *e)
160 {
161     int j = 0;
162     LinkList p = L;
163     while(p->next)
164     {
165         j++;
166         p=p->next;
167     }
168     *e = j;
169     return OK;
170 }
171 int _tmain(int argc, _TCHAR* argv[])
172 {
173     LinkList *L=(LinkList*)malloc(sizeof(Node));
174     int listLength = 0;//链表长度
175     CreateListTail(L,5);//尾插法创建一个链表
176     ReadList(*L);//输出1 2 3 4 5
177     int endData = 0;
178     GetEndElem(*L,&endData);
179     cout<<"最后一个元素:"<<endData<<endl;
180     int localData=0;
181     GetElem(*L,2,&localData);//获取第二个元素
182     cout<<localData<<endl;//输出2
183     int insertElem=9;
184     ListInsert(L,2,&insertElem);//在第二个位置插入9
185     ReadList(*L);//输出1 9 2 3 4 5
186     GetListLength(*L,&listLength);//获取链表长度
187     cout<<"链表长度:"<<listLength<<endl;//输出 6
188     ListDelete(L,3,&insertElem);//把第三个位置的数2删除,返回给insertElem
189     ReadList(*L);//输出1 9 3 4 5
190     GetListLength(*L,&listLength);//获取链表长度
191     cout<<"链表长度:"<<listLength<<endl;
192     cout<<insertElem<<endl;//输出2
193     ClearList(L);//整表删除
194     ReadList(*L);//空表没输出了
195     return 0 ;
196 }