一直以来我都希望我的数据结构能达到一个比较高的水平:就像套用公式一样的把各种数据结构写出来。由于算法是基于数据结构的,所以如果要想把算法搞好,那数据结构功底一定要扎实。
我的目标:很熟悉各种数据结构,把算法问题当作简单的搭积木问题。(下面注意看注释)
今天复习了一下链表。
一、单链表
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");
}
最后,感觉结点的删除没啥好分析的,就不作记录了。
|