連結清單



1．編寫頭檔案

#include<stdio.h>

#include<stdlib.h>

#define 

datatype 

int

struct

node

{

num;           

//編号

datatype

data;     

//存儲的資料

node *pnext;

};

typedef

node; 

//簡寫

//函數設計的思想

//改變一個變量需要變量的位址，改變指針需要指針的位址

//不用二級指針，必須要用傳回值指派

//增加，删除，查詢，修改，排序，逆轉

void 

backaddnode(node

**ppnode,

num,

data);//增加節點

node *

backaddnodea(node

*pnode,

data);//

void

showallnode(node

*pnode);//顯示所有的節點

searchfirst(node

num);//查詢

change(node

oldnum,

newnum);//修改失敗傳回0，成功傳回1

rev(node

*pnode);//連結清單的逆轉

node * delete(node

num);//删除

insert(node

findnum,

newnum,

data);//實作插入，前面插入

sort(node

char

ch);//ch==> ch==<

2．編寫連結清單的實作代碼

#include

"linknode.h"

//增加節點

data)

//添加節點，需要先增加節點

node *pnewnode

= (node *)malloc(sizeof(node));

pnewnode->num

= num;  

//指派

pnewnode->data

= data;

pnewnode->pnext

= null;//尾部

//如果連結清單為null

if (*ppnode

== null)

//存儲建立節點的位址

*ppnode =

pnewnode;

}

else

node *p

= *ppnode;//等于頭結點

while (p->pnext

!= null)

   //一直循環到最後一個節點的位址

p =

p->pnext;

//表示尾部插入

p->pnext

= pnewnode;

//定義新節點

= num;

= null;

if (pnode

pnode =

//等于頭結點

= pnode;

//一直循環到最後一個節點的位址

//尾部插入

return

pnode;

//顯示所有的節點

*pnode)

printf("列印連結清單:\n");

while(p

printf("%p,%p,%d,%d\n",

p,

p->pnext,

p->num,

p->data);

//查詢

num)

//for循環

for (p

p !=

null;p=p->pnext)

if (num

== p->num)

//

傳回找到的位址

p;

break;

null;

//修改失敗傳回0，成功傳回1

newnum)

aaa:if

(pnode !=

null)

//查找

if (oldnum

== pnode->num)

pnode->num

= newnum;

return 1;

pnode->pnext;

goto

aaa;

return 0;

//連結清單的逆轉

node *p1,

*p2, *p3;

p1 =

p2 =

p3 =

null;//避免野指針

//表示為空連結清單或者隻有一個節點的情況下，直接傳回

== null ||

pnode->pnext

//傳回頭結點

//p2 == null時表示p1是最後一個節點了。

while (p2!=null)

//這裡p3相當于中間變量，用于儲存p2最開始的指向

p2->pnext;//布局第三個點

//将指針位址轉向

p2->pnext

= p1;

//循環向後移動

p2;

p3;

//将最開始的頭節點的next變成null

//改變頭節點位置，由最開始的位置變成最後節點

p1;

/************************************************************************/

/*

删除含有num的節點，删除節點的時候需要使用兩個節點，其中一個節點要儲存*/

要删除節點的上一個節點的位置                                        

*/

node *p1

= null, *p2

//如果p1==null說明p2已經是最後節點

while (p1

if (p1->num

== num)

//p1儲存了要删除節點的位址，實際上p1就是要删除的那個節點

//p2儲存p1上一個節點的位置

p1->pnext;

//如果要删除的節點恰好是首節點

if (p1

== pnode)

//斷開與p1的關系，跳過了這個節點

//删除節點

free(p1);

//中間和末尾删除的情況

//這時候把p2代表的那個節點位址指向p1的下一個節點

= p1->pnext;

//因為首位址改變了，是以要傳回首位址的值

實作插入，前面插入                                                  */

同樣要借助兩個節點，一個節點存儲查找到的目标節點，另外一個節點存儲  

目标節點前的一個節點                                                */

*p2;

== findnum)

//p1儲存了要插入節點的位址

//p1是查找到的目标節點，p2儲存其上一個節點的位址

p1->pnext; 

//先前循環

//生成節點

//表示找到的恰好是首節點

== p1)

//新節點的下一個節點是頭節點，這裡下面也可以換成p1

//這種方式表示的是頭節點

//将新節點的目标位址指向目标節點

//将p1的上一個節點的下一個的位址指派成新節點的位置

當傳遞'>'的時候表示的是降序排列                                     */

當傳遞'<'的時候表示的是升序排列                                     */

ch)

if (ch

== '<')

for (node

*p1 =

p1 !=

null;p1=p1->pnext)

*p2 =

p2 !=

null;p2=p2->pnext)

> p2->num)

    //這裡的node作為中間變量

tnode;

tnode.num

= p1->num;

p1->num

= p2->num;

//交換資料

p2->num

= tnode.num;

//交換data資料

tnode.data

= p1->data;

p1->data

= p2->data;

p2->data

= tnode.data;

p1=p1->pnext)

null;p2

= p2->pnext)

< p2->num)

//作為中間變量

= tnode.num; 

//交換data

        tnode.data

3.編寫main.c測試編寫的連結清單

main(int

argc,char

*argv[])

//定義一個頭結點(這是最開始要做的)

node *pnode

//backaddnode(&pnode, 1, 1);

//backaddnode(&pnode, 2, 12);

//backaddnode(&pnode, 3, 14);

//showallnode(pnode);

backaddnodea(pnode,

1, 1);

//pnode = backaddnodea(pnode, 12, 11);

3, 111);

14, 1111);

5, 11111);

//pnode = backaddnodea(pnode, 16, 111111);

showallnode(pnode);

printf("改變參數\n");

change(pnode,

14, 141414);

//反轉

printf("反轉\n");

rev(pnode);

//删除

pnode = delete(pnode,1);

pnode = delete(pnode,

3);

//插入

insert(pnode,

3, 3, 333);

1, 13, 1333);

//排序

sort(pnode,

'<');

'>');

node *pfind

= searchfirst(pnode,

5);

if (pfind

printf("沒有找到");

printf("%p,%d,%d,%p\n",

pfind,

pfind->num,

pfind->data,

pfind->pnext);

getchar();