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