|
|
一直以來(lái)我都希望我的數(shù)據(jù)結(jié)構(gòu)能達(dá)到一個(gè)比較高的水平：就像套用公式一樣的把各種數(shù)據(jù)結(jié)構(gòu)寫(xiě)出來(lái)。由于算法是基于數(shù)據(jù)結(jié)構(gòu)的，所以如果要想把算法搞好，那數(shù)據(jù)結(jié)構(gòu)功底一定要扎實(shí)。
我的目標(biāo)：很熟悉各種數(shù)據(jù)結(jié)構(gòu)，把算法問(wèn)題當(dāng)作簡(jiǎn)單的搭積木問(wèn)題。（下面注意看注釋）
今天復(fù)習(xí)了一下鏈表。
一、單鏈表
typedef struct student
{
struct student *next; //由于C語(yǔ)言是從上到下一行一行進(jìn)行編譯，所以這里不能是stu *next;
char *name;
}stud;
stud *Creat( int n ) //創(chuàng)建一個(gè)返回是結(jié)構(gòu)體類型的指針，這里的n是創(chuàng)建的節(jié)點(diǎn)個(gè)數(shù)，由用戶決定
{
int i;
stud *h, *p, *t; //三個(gè)指針是此方法創(chuàng)建鏈表的必要條件，一個(gè)頭指針，另外兩個(gè)輪流交換地址（指針指向）
h = ( stud * )malloc( sizeof( stu ) );
h -> next = NULL; //初始化
h -> name[0] = '\0'; //把數(shù)組的第一個(gè)空間取'\0'時(shí)，后面的空間都是'\0'
t = h; //交換地址開(kāi)始
for( i = 0;i < n;i++ )
{
p = ( stud * )malloc( sizeof( stu ) );
t -> next = p;
p -> next = NULL; //中間就是一個(gè)輪流交換的過(guò)程，把各種指針指向正確的位置就行了
//技巧就是就是只寫(xiě)每產(chǎn)生一個(gè)新結(jié)點(diǎn)時(shí)候的操作
printf("請(qǐng)輸入學(xué)生姓名：");
scanf("%s",p -> name );
t = p; //讓t指向新結(jié)點(diǎn)，可以理解成“又一波循環(huán)的開(kāi)始”,每次把其他指針搞定之后一定要這步操作
}
p -> next = NULL; //如果是循環(huán)單鏈表的話這里改成 p ->next = h;
return h; //返回頭指針
}
二、雙向鏈表
typedef struct student
{
struct student *prior, *next; //比單鏈表多了一個(gè)prior指針而已,下面的操作十分類似
char name[10];
}stud;
stud *Creat( int n )
{
int i;
stud *h, *p, *t; //三個(gè)指針是此方法創(chuàng)建鏈表的必要條件，一個(gè)頭指針，另外兩個(gè)輪流交換地址
h = ( stud * )malloc( sizeof( stu ) );
h -> next = NULL; //初始化
h -> prior = NULL;
h -> name[0] = '\0';
t = h;
for( i = 0;i < n;i++ )
{
p = ( stud * )malloc( sizeof( stu ) );
p -> next = NULL;
p -> prior = t; //這里面的操作其實(shí)很簡(jiǎn)單，就是只寫(xiě)每產(chǎn)生一個(gè)新結(jié)點(diǎn)時(shí)候的操作，主要就是指針操作嘛
t -> next = p;
printf("請(qǐng)輸入學(xué)生姓名：");
scanf("%s",p -> name );
t = p; //最后別忘了把 t指向新結(jié)點(diǎn)
}
t -> next = NULL; //有些書(shū)上加了這步，但我覺(jué)得沒(méi)有必要，得好好思考一下
return h;
}
三、鏈表里面的查找
stud *search( stud *h, char *Name )//對(duì)于不是很長(zhǎng)的鏈表，完全可以從頭結(jié)點(diǎn)開(kāi)始查找。查找的依據(jù)是姓名
{
stud *t; //因?yàn)橐樦Y(jié)點(diǎn)的next走下去，需要一個(gè)變量t和next輪流交換
t = h->next;
while( p )
{
if( strcmp( t -> name,Name) == 0 )
{ //說(shuō)明找到了
return t;
}
else
t = t->next; //指向下一結(jié)點(diǎn)的通用方法
}
printf("NOT FIND !\n");
}
最后，感覺(jué)結(jié)點(diǎn)的刪除沒(méi)啥好分析的，就不作記錄了。
|
評(píng)分
-
查看全部評(píng)分
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
