澳门太阳娱乐集团官网-太阳集团太阳娱乐登录

单链表的基本操作
分类:脚本专栏

实现单链表的基本操作(创建,查询,插入,删除,销毁,归并,排序)

单链表的基本操作(第二篇),单链基本操作

与第一篇不同的点是单链表的建立方法,以及合并两个有序链表。

知识点介绍:

1.何为野指针?

太阳集团太阳娱乐登录,野指针指指向一个已删除的对象或未申请访问受限内存区域的指针。与空指针不同,野指针无法通过简单地判断是否为NULL避免,而只能通过养成良好的编程习惯来尽力减少。对野指针进行操作很容易造成程序错误。

2.野指针的成因主要有两种:

(1)、指针变量没有被初始化。任何指针变量刚被创建时不会自动成为NULL指针,它的缺省值是随机的,它会乱指一气。所以,指针变量在创建的同时应当被初始化,要么将指针设置为NULL,要么让它指向合法的内存。

(2)、指针p被free或者delete之后,没有置为NULL,让人误以为p是个合法的指针。别看free和delete的名字恶狠狠的(尤其是delete),它们只是把指针所指的内存给释放掉,但并没有把指针本身干掉。通常会用语句if (p != NULL)进行防错处理。很遗憾,此时if语句起不到防错作用,因为即便p不是NULL指针,它也不指向合法的内存块。(引用别人博客上的解释)

如果程序定义了一个指针,就必须要立即让它指向一个我们设定的空间或者把它设为NULL,如果没有这么做,那么这个指针里的内容是不可预知的,即不知道它 指向内存中的哪个空间(即野指针),它有可能指向的是一个空白的内存区域,可能指向的是已经受保护的区域,甚至可能指向系统的关键内存,如果是那样就糟 了,也许我们后面不小心对指针进行操作就有可能让系统出现紊乱,死机了。

下面程序在开始写的时候就出现过这种情况,所以上面介绍了一下野指针,具体地方程序中注释出来了。

单链表结点的定义和初始化以及打印函数与第一篇相同,这里不再列出。

顺序输入n个元素的值,建立带表头结点的单链表:

//建立单链表
void CreatlistR(LinkLNode *head, int n)
{
 LinkLNode *node;
 head->next = NULL;
 for (int i = 0; i < n; i++)
 {
  node = (LinkLNode*)malloc(sizeof(LinkLNode));
  scanf("%d", &node->data);
  head->next = node;
  head = node;
 }
 head->next = NULL;//开始没加这句,导致exe停止工作  
http://www.bkjia.com/Cyy/1219876.htmlwww.bkjia.comtruehttp://www.bkjia.com/Cyy/1219876.htmlTechArticle单链表的基本操作(第二篇),单链基本操作 与第一篇不同的点是单链表的建立方法,以及合并两个有序链表。 知识点介绍: 1.何为野指...

单链表,单链表的基本操作

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<malloc.h>
  4 
  5 typedef int Elemtype;
  6 
  7 typedef struct Node{
  8     int data;
  9     struct Node* next;
 10 }Node;
 11 
 12 typedef struct Node* LinkList;
 13 
 14 void InitLinkList(LinkList *L);
 15 void DestoryList(LinkList* L);
 16 void ClearList(LinkList *L);
 17 void HeadCreateList(LinkList*,int);
 18 void TailCreateList(LinkList*,int);
 19 void DisplayList(LinkList);
 20 
 21 //void InitLinkList(Node** L){
 22 //    *L = (LinkList)malloc(sizeof(struct Node));
 23 //    (*L)->next = NULL;
 24 //    //alternation 
 25 //}
 26 void InitList(LinkList *L){
 27     *L = (LinkList)malloc(sizeof(struct Node));
 28     (*L)->next = NULL;
 29 }
 30 void DestoryList(LinkList* L){
 31 /*
 32     LinkList p = *L,q;
 33     printf("%d %dn",p,*L); //p == *L == 7279912
 34     while(p){
 35         q = p->next;
 36         free(p);
 37         p = q;           //last step p = NULL
 38     }
 39     printf("%d %d",p,*L);  //p = 0;*L = 7279912
 40     free(*L);
 41     printf("%d ",*L);      //*L = 7279912
 42 analise the reason for error by the result of "printf"
 43 free(p) is release the block of memory pointed by P,
 44 dose not change pointer p itself.  NULL == 0
 45 */
 46     LinkList q;
 47     while(*L){
 48         q = (*L)->next;
 49         free(*L);
 50         *L = q;
 51     }
 52 }
 53 void ClearList(LinkList *L){
 54     //ClearList(&L);
 55 //    LinkList p = *L;
 56 //    LinkList q;
 57 //
 58 //    TailCreateList(&L,4);
 59 //    DisplayList(L);
 60 //    ClearList(&L);
 61 //    TailCreateList(&L,4);
 62 
 63     LinkList p = (*L)->next;
 64     LinkList q;
 65     while(p){
 66         q = p -> next;
 67         free(p);
 68         p = q;
 69     }
 70     (*L)->next = NULL;
 71     printf("LinkList has been clear!n");
 72 }
 73 void ListEmpty(LinkList L){
 74     if(L->next == NULL)
 75         printf("List empty!n");
 76     else 
 77         printf("Exit Element in Listn");
 78 }
 79 int ListLength(LinkList L){
 80     LinkList p = L->next;
 81     int count = 0;
 82     while(p){
 83         count+=1;
 84         p = p->next;
 85     }
 86     return count;
 87 }
 88 int GetElem(LinkList L,int index,int *r){
 89     int length = ListLength(L);
 90     if(index < 1 || index > length){
 91         return 0; //failed
 92     }else{
 93         int j = 0;
 94         while(j<index){
 95             L = L->next;
 96             j++;
 97         }
 98         *r = L->data;
 99         return 1;
100     }
101 }
102 void GetPriorElem(LinkList L,int current_elem,int *priorElement){
103 /*
104     LinkList p = L->next;
105     LinkList q;
106     if(p == NULL){
107         printf("List is Empty!n");
108         exit(1);
109     }
110     if(p->data == current_elem){
111         printf("the current element is first!n");
112         exit(1);
113     }
114     q = p->next;
115     while(q && q->data != current_elem){
116         p = q;q = q->next;
117     }
118     if(q == NULL){
119         printf("there is no current in List!n");
120         exit(1);
121     }
122     else
123         *priorElement = p->data;
124 */
125 /*
126 the promise of the following code is that the 
127 current_element is not the first element of the
128 list and does not consider the case of the list
129 for NULL
130 */
131     LinkList p = L->next; //p point first node
132     LinkList q;
133     while(p->next){
134         q = p->next;
135         if(q->data == current_elem){
136             *priorElement = p->data;
137             break;
138         }
139         p = q;
140     }
141     if(p->next == NULL)
142         printf("there is no current_element in Listn");
143 }
144 void GetNextElem(LinkList L,int current_elem,int* next_elem){
145     LinkList p = L->next;
146     LinkList q;
147     if(p == NULL){
148         printf("List is Empty!n");
149         exit(1);
150     }
151     while(p->next){
152         q = p->next;
153         if(p->data == current_elem){
154             *next_elem = q->data;
155             return;
156         }
157         p = q;
158     }
159     printf("GetNextElement is Failed!n");
160 }
161 void HeadCreateList(LinkList* L,int n){
162     LinkList s;
163     int i;
164     int e;
165     for(i = 1;i <= n; i++){
166         printf("enter %d integer: ",i);
167         scanf("%d",&e);
168         s = (LinkList)malloc(sizeof(struct Node));
169         s->data = e;
170         s->next = (*L)->next;
171         (*L)->next = s;
172     }
173     printf("n");
174 }
175 void TailCreateList(LinkList* L,int n){
176     LinkList tail = *L;
177     LinkList s;
178     int i;
179     int e;
180     for(i = 1;i <= n; i++){
181         printf("enter %d integer: ",i);
182         scanf("%d",&e);
183         s = (LinkList)malloc(sizeof(struct Node));
184         s->data = e;
185         tail->next = s;
186         s->next = NULL;
187         tail = s;
188     }
189     printf("n");
190 }
191 void ListInsert(LinkList* L,int index,int e){
192 /*
193 //insert element before index
194     LinkList q;
195     LinkList p = *L;
196     LinkList s;
197     int count = 0;
198     while(p->next){
199         q = p->next;
200         count += 1;
201         if(count == index){
202             s = (LinkList)malloc(sizeof(struct Node));
203             s -> data = e;
204             p->next = s;
205             s->next = q;
206             break;
207         }
208         p = q;
209     }
210     if(p->next == NULL){
211         printf("InsertList Index Error!n");
212     }
213 */
214 //options
215     LinkList p = *L;
216     LinkList s;
217     int count = 0;
218     while(p && count<index-1){
219         p = p->next;
220         count += 1;
221     }
222     if(p){
223         s = (LinkList)malloc(sizeof(struct Node));
224         s->data = e;
225         s->next = p->next;
226         p->next = s;
227     }
228     if(p == NULL){
229         printf("InsertList Index Error!n");
230     }
231 }
232 void ListDelete(LinkList *L,int index,int* e){
233     LinkList p = *L;
234     int count = 0;
235     while(p && count < index - 1){
236         p = p->next;
237         count += 1;
238     }
239     if(p){
240         if(p->next){
241             *e = p->next->data;
242             p->next = p->next->next;
243         }
244         else
245             printf("DeleteList Index Errorn");
246     }
247     if(p == NULL)
248         printf("DeleteList Index Errorn");
249 }
250 void DisplayList(LinkList L){
251     if(L == NULL){
252         printf("List has been destory!n");
253     }else
254     {
255         LinkList p = L;
256         while(p -> next){
257             printf("%d ",p->next->data);
258             p = p->next;
259         }
260         printf("n********displayList executed!n");
261     }
262 }
263 void main(){
264 //    Node L;
265 //    LinkList L1 = &L;
266 //    InitLinkList(&L1);
267 
268     LinkList L;
269     InitList(&L);
270     TailCreateList(&L,4);
271     DisplayList(L);
272     ClearList(&L);
273     ListEmpty(L);
274     DisplayList(L);
275     DestoryList(&L);
276     DisplayList(L);
277 
278     InitList(&L);
279     TailCreateList(&L,5);
280     printf("Length of List is: %dn",ListLength(L));
281     DisplayList(L);
282 
283     int r0;
284     if(GetElem(L,5,&r0)){
285         printf("getelement index=5 is : %dn",r0);
286     }
287     else
288         printf("getelement index=5 is Failedn");
289 
290     if(GetElem(L,6,&r0)){
291         printf("getelement index=6 is : %dn",r0);
292     }
293     else
294         printf("getelement index=6 is Failedn");
295 
296     int r1;
297     GetPriorElem(L,3,&r1);
298     printf("the result of GetPriorElement(3) is: %dn",r1);
299 
300     int r2;
301     GetNextElem(L,3,&r2);
302     printf("the result of GetNextElement(3) is: %dn",r2);
303     ListInsert(&L,5,999);
304     DisplayList(L);
305 
306     int r3;
307     ListDelete(&L,2,&r3);
308     DisplayList(L);
309     printf("execute ListDelete index=2 is %dn",r3);
310 }

太阳集团太阳娱乐登录 1

1 #includestdio.h 2 #includestdlib.h 3 #includemalloc.h 4 5 typedef int Elemtype; 6 7 typedef struct Node{ 8 int data; 9 struct Node* next; 10...

创建链表 La链表初始化成功请输入La中元素的个数:9请输入第 9 个元素:9请输入第 8 个元素:8请输入第 7 个元素:7请输入第 6 个元素:6请输入第 5 个元素:5请输入第 4 个元素:4请输入第 3 个元素:3请输入第 2 个元素:2请输入第 1 个元素:11  2  3  4  5  6  7  8  9创建链表 Lb链表初始化成功请输入Lb中元素的个数:5请输入第 5 个元素:9请输入第 4 个元素:7请输入第 3 个元素:5请输入第 2 个元素:3请输入第 1 个元素:11  3  5  7  9合并链表 La Lb链表初始化成功1  1  2  3  3  4  5  5  6  7  7  8  9  9请按任意键继续. . .

//----------------------------单链表的存储表示-------------------------------#include<stdio.h>#include<stdlib.h>#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define OVERFLOW -1typedef int Status;typedef int ElemType;typedef struct LNode{    ElemType data;      struct LNode *Next;}LNode, *LinkList;Status InitList_L(LinkList *L) ;Status CreateList_L(LinkList *L, int n);Status ListInsert_L(LinkList *L, int i, ElemType e);Status ListDelete_L(LinkList *L, int i, ElemType *e);Status DisplayList_L(LinkList *L);Status GetElem_L(LinkList L, int pos, ElemType *e);Status LocateElem_L(LinkList L,int *pos, ElemType e);Status MergeList_L(LinkList *La, LinkList *Lb, LinkList *Lc);int main(){    LinkList La,  Lb,  Lc;    int countA,countB;    printf_s("创建链表 La n");    InitList_L(&La);    printf_s("请输入La中元素的个数:");    scanf_s("%d", &countA);    CreateList_L(&La, countA);    DisplayList_L(&La);    printf_s("创建链表 Lb n");    InitList_L(&Lb);    printf_s("请输入Lb中元素的个数:");    scanf_s("%d", &countA);    CreateList_L(&Lb, countA);    DisplayList_L(&Lb);    printf_s("合并链表 La Lb n");    InitList_L(&Lc);    MergeList_L(&La, &Lb, &Lc);    DisplayList_L(&Lc);    system("pause");}Status InitList_L(LinkList *L){       *L = malloc(sizeof;          if(!(*L))        {                exit(0);       }       (*L)->Next = NULL;    printf_s("链表初始化成功n");    return OK;}// InitList_LStatus CreateList_L(LinkList *L, int n){    int i;    LinkList p;    for (i = n; i > 0; --i)    {        p =  malloc(sizeof;        printf_s("请输入第 %d 个元素:", i);        scanf_s("%d", &(p->data));        p->Next = ->Next;        (*L)->Next = p;    }    return OK;}// CreateList_LStatus ListInsert_L(LinkList *L, int i, ElemType e){    LinkList s, p;    int j;    p = *L;    j = 0;    //寻找第 i-1 个节点    while (p && j < i - 1)    {        p = p->Next;        ++j;    }    if (!p || j > i - 1)    {        return ERROR;    }    s =  malloc(sizeof;    s->data = e;    s->Next = p->Next;    p->Next = s;    return OK;}// ListInsert_LStatus ListDelete_L(LinkList *L, int i, ElemType *e){    LinkList p, q;    int j;    p = *L;    j = 0;    while ( p->Next && j < i - 1)    {        p = p->Next;        ++j;    }    if (!(p->Next) || j > i - 1)    {        return ERROR;    }    q = p->Next;    p->Next = q->Next;    e = &(q->data);    free;    return OK;}// ListDelete_LStatus DisplayList_L(LinkList *L){    LinkList p = ->Next;    while (p != NULL)    {        printf_s("%d  ", p->data);        p = p->Next;    }    printf_s("n");    return OK;}// DisplayList_LStatus GetElem_L(LinkList L, int pos, ElemType *e){    LinkList p;    int j;    p = L->Next;    j = 1;    while (p && j < pos)    {        p = p->Next;        ++j;    }    if (!p || j < pos)    {        return ERROR;    }    e = &(p->data);    return OK;}// GetElem_LStatus LocateElem_L(LinkList L,int *pos, ElemType e){      LinkList p;      int i = 1;     p = L->Next;      while(p && (p->data != e))     {           p = p->Next;          ++i;     }      if(!p)     {          return ERROR;    }     *pos = i;    return OK;}// LocateElem_LStatus DestroyList_L(LinkList L)      //销毁链表{     LinkList p ;       while     {          p = L;         L = L->Next;          free;      }      L = NULL;    return OK;}// DestroyList_LStatus MergeList_L(LinkList *La, LinkList *Lb, LinkList *Lc){    LinkList pa, pb, pc;    pa = ->Next;    pb = ->Next;    *Lc = pc = *La;    while (pa && pb)    {        //printf_s("pa->data:%d  pb->data:%dn",pa->data,pb->data);        if (pa->data <= pb->data)        {            pc->Next = pa;            pc = pa;            pa = pa->Next;        }        else        {            pc->Next = pb;            pc = pb;            pb = pb->Next;         }    }    pc->Next = pa ? pa : pb;    free(*Lb);    return OK;}// MergeList_L

本文由澳门太阳娱乐集团官网发布于脚本专栏,转载请注明出处:单链表的基本操作

上一篇:没有了 下一篇:没有了
猜你喜欢
热门排行
精彩图文