数据结构 - 链表

0.链表的定义

1.单链表

        单链表一个结点 = data + next(指针) ，所以其存储结构是随机存储结构

2.双链表

        双链表一个结点 = prior(指针) + data + next(指针) ，所以其存储结构是随机存储结构

一.单链表

1.单链表的结构

        单链表一个结点 = data + next(指针)

2.单链表结构体的定义

typedef int datatype;typedef struct node
{datatype data;struct node *next; 
}listnode;

3.创建一个空的单链表

/*** @description:            创建一个空的单链表
*/
listnode *list_create(void)
{listnode *p = NULL;/* 1.申请空间 */p = (listnode *)malloc(sizeof(listnode));if(NULL == p){printf("create list faild\n");return NULL;}/* 2.初始化头结点 */p->data = 0;p->next = NULL;return p;
}

4.使用键盘输入创建并初始化单链表

/*** @description:            键盘输入创建单链表* @param       :           无* @return      :           指向链表的指针
*/
listnode *list_create_init(void)
{/* h指向头结点，r指向尾结点,q指向新结点 */listnode *h,*r,*q;datatype value;     //接收键盘输入的值/* 1.申请空间 */h = (listnode *)malloc(sizeof(listnode));if(NULL == h){printf("create list faild\n");return NULL;}r = h;                  //初始情况，尾结点就是首结点/* 2.初始化头结点 */h->data = 0;h->next = NULL;/* 3.利用尾插，循环插入新的结点 */while(1){printf("input new node ->\n");printf("input -1 : exit\n");scanf("%d",&value);if(-1 == value){break;}/* 3.创建新的结点 */q = (listnode *)malloc(sizeof(listnode));if(NULL == q){printf("create list faild\n");return NULL;}q->data = value;q->next = NULL;r->next = q;        //尾结点的next的字段指向新的结点r = q;              //尾结点指针向后移动}return h;
}

5.向单链表中头插

/*** @description:            向单链表中使用头插，插入一个结点* @param - h       :       要操作的链表的首结点的指针* @param - x       :       要插入的结点的data字段数据* @return          :       0 成功，其他 失败
*/
int insert_head_list(listnode *h , datatype value)
{listnode *p = list_create();if(NULL == p){printf("insert into linklist faild!\n");return -1;}p->data = value;p->next = h->next;h->next = p;return 0;
}

6.向单链表中尾插

7.打印单链表所有的结点

/*** @description:            打印链表全部的结点* @param - h       :       要操作的单链表* @return          :       无
*/
void list_show(listnode *h)
{/* 循环打印，直到某个结点的指针为NULL，则表示是最后一个结点 */while(h->next){printf("%d ",h->next->data);h = h->next;                    //结点指向向后移动}printf("\n");
}

8.按序号查找结点

/*** @description:            按照序号查找链表中的结点* @param - h       :       要操作的链表* @param - pos     :       结点的序号* @return          :       查找到的结点的指针,若为NULL，则查找失败
*/
listnode *Get_Linklist(listnode *h,int pos)
{listnode *p = h;        //记录当前结点位置int j = -1;      /* 结点序号必须大于等于0 */if(0 > pos)return NULL;   /* 遍历链表，直到 j = pos （成功找到指定序号的结点）|| （当前结点位置已经到了最后一个结点） */while(p->next && j < pos){p = p->next;        //结点向后移动一个位置j++;}/* 若以指定序号找到了结点,则返回找到的结点的指针 */if(j == pos)      {return p;}/* 若没有找到，则返回NULL */elsereturn NULL;return NULL;
}

9.按结点的数据查找结点

/*** @description:            按照指定结点的数据查找结点* @param - h       :       要操作的链表的头结点* @param - value   :       指定要查找的值* @return          :       查找到的结点的指针,若返回NULL则为失败
*/
listnode *List_Locate(listnode *h,datatype value)
{listnode *p = h;        //记录当前结点位置/* 遍历链表，直到 （结点位置已经到了最后一个结点）||（查找到了指定的结点） */while((p->next) && (p->data != value)){p = p->next;}/* 若当前结点的data字段 == value */if(p->data == value)return p;elsereturn NULL;return NULL;
}

10.向单链表中某个结点前插入一个结点

/*** @description:            向单链表的某个结点前插入一个结点* @param - h       :       要操作的链表的头结点指针
*/
int Insert_Linklist_before(listnode *h,datatype value,int pos)
{listnode *p,*q;/* 位置必须大于等于0 */if(0 > pos){return -1;}/* 1.申请一个新结点填充数据 */p = list_create();p->data = value;p->next = NULL;if(pos == 0)       //若为0,则直接在首结点头插{p->next = h->next;h->next = p;return 0;}/* 2.找到要插入的结点的前驱结点 */q = Get_Linklist(h,pos-1);if(NULL == q)               //若没有找到指定结点的前驱结点return -1;/* 3.将该结点,插入到指定结点s的前驱结点的后面 */p->next = q->next;q->next = p;return 0;
}

11.删除指定序号的结点

/*** @description:            删除指定序号的结点* @param - h       :       要操作的链表的首结点指针* @param - pos     :       指定的结点的序号* @return          :       0 成功;其他 失败
*/
int Delete_Linklist_bypos(listnode *h,int pos)
{listnode *p,*q;         //q用来指向要删除的结点，p用来指向要删除结点的前驱结点/* 序号必须 >= 0 */if(0 > pos)return -1;if(0 == pos)            //要删除第 0 个结点{q = h->next;            //q指向第 0 个结点h->next = q->next;      //首结点的指针字段指向第 1 个结点 free(q);                //删除第 0 个结点}/* 删除其他的结点 */else{p = Get_Linklist(h,pos-1);      //p指向前驱结点     a(i-1)q = p->next;                    //q指向要删除的结点  a(i)/* 若没有前驱结点 || 没有指定的结点 */if(NULL == p || NULL == q)return -1;p->next = q->next;              //结点 a(i-1) 的指针字段指向结点 a(i+1)free(q);                        //删除结点 a(i)}return 0;
}

12.删除指定数值的结点

/*** @description:            删除指定 value 的结点* @param - h       :       要操作的链表的头结点指针* @param - value   :       指定的结点 data 字段的数据* @return          :       0为成功 ; 其他为失败
*/
int Delete_Linklist_byvalue(listnode *h,datatype value)
{listnode *p,*q;             // p 指向要删除结点的前驱结点，q 指向要删除的结点p = h;/* 找到指定结点的前驱结点 p , p->next->data 就是指定结点的数据段的值*/while(p->next->next && (p->next->data != value)){p = p->next;}if(p->next->data == value)          //p->next是指定结点       {q = p->next;                    //q 指向指定结点}elsereturn -1;p->next = q->next;free(q);return 0;
}

13.单链表倒置

/*** @descritpion:            倒置链表* @param - h       :       要操作的链表头结点指针* @return          :       0为成功;其他为失败
*/
void Reverse_Linklist(listnode *h)
{listnode *p,*q;                 p = h->next;            //p 指向 a(0) 结点h->next = NULL;while(p != NULL){q = p;p = p->next;q->next = h->next;h->next = q;}
}

14.单链表的有序插入

/*** @description:            向单链表中有序插入一个结点* @param - h       :       要操作的链表首结点指针* @param - value   :       要插入的结点的值
*/
int Insert_order_Linklist(listnode *h,datatype value)
{listnode *p,*q;/* 为新结点申请空间 */p = (listnode *)malloc(sizeof(listnode));if(NULL == p){return -1;}p->next = NULL;p->data = value;q = h;/* 遍历查找比新结点 data 字段大的结点(q->next)，找到了就头插在该结点前 */while(q->next && q->next->data <= value)       {q = q->next;}if(NULL == q->next)             //所有的结点的 data 字段都 <= 新结点的 data 字段{q->next = p;}else if(q->next->data > value){p->next = q->next;q->next = p;}return 0;
}

15.单链表的排序（直接插入排序）

/*** @description:            单链表排序（直接插入排序）* @param - h       :       要操作的链表* @return          :       无
*/
void Linklist_Sort(listnode *h)
{listnode *p,*q,*r;p = h->next;            //指向 a(0)h->next = NULL;         //把头结点从链表上分开while(p){q = p;              // q、p 指向 a(0) 结点p = p->next;        //p往后移动r = h;while(r->next && r->next->data <= q->data){r = r->next;}q->next = r->next;r->next = q;}
}

二.单向循环链表

1.单向循环链表的结构

        单链表的最后一个结点的 *next 字段为 NULL。单向循环链表的最后一个结点的 *next 字段为首结点的指针。

三.双向循环链表

1.双向循环链表的结构

2.双向链表的结构体定义

typedef int data_t;/* 双向链表结构体 */
typedef struct double_linklist
{data_t data;struct double_linklist *prior,*next;
}dlinklist;

3.使用键盘输入创建一个双向循环链表

注意：当只有头结点时，其

/*** @description:            用户输入创建一个循环双链表* @param -         :       无* @return          :       创建的双链表的首结点指针
*/
dlinklist * dlist_create(void)
{dlinklist *h,*r,*p;     // h 为头结点的指针，r 指向链表的最后一个结点，p 指向新创建的结点 int num = 0;/* 1.创建一个头结点 */h = (dlinklist *)malloc(sizeof(dlinklist));if(NULL == h){printf("dlinklist create failed\n");return NULL;}/* 2.头结点初始化，next 和 prior 都指向自己 */h->prior = h;h->next = h;r = h->prior;/* 3.键盘输入要创建的结点的 data 段数据 */while(1){printf("input node data:\n");printf("input -1 break!\n");scanf("%d",&num);if(-1 == num){break;}else{/* 创建一个新的结点 p */p = (dlinklist *)malloc(sizeof(dlinklist));if(NULL == p){printf("dlinklist create failed!\n");return -1;}p->data = num;/* 对尾结点进行尾插 */p->prior = r;p->next = r->next;r->next = p;h->prior = p;r = p;}}return h;
}   

4.打印双向循环链表

/*** @description:            打印循环双链表的内容* @param - h       :       要操作的双链表的首结点指针* @return          :       无
*/
void dlist_show(dlinklist *h)
{dlinklist *p;p = h->next;if(p == h){printf("the linklist is empty!\n");return ;}while(p != h){printf("%d ",p->data);p = p->next;}printf("\n");
}

5.按序号查找双向循环链表的结点

/*** @description:            按序号查找双向循环链表的结点* @param - h       :       要操作的双向循环链表的首结点指针* @param - pos     :       指定结点的序号
*/
dlinklist *Dlinklist_Get_Bypos(dlinklist *h,int pos)
{dlinklist *p = h;           //指向当前的结点int i = -1;             //从首结点出发if(pos < 0){printf("the pos is invalid!\n");return NULL;}while(i < pos){p = p->next;i++;/* 若遍历到了最后的一个结点 */if(p == h)return NULL;}if(i == pos){return p;}}

6. 按值查找双向循环链表中的结点

/*** @description:                按值查找双向循环链表中的结点* @param - h       :           要操作的链表的首结点指针* @param - value   :           要查找的结点的值* @return          :           找到的结点的指针
*/
dlinklist *Dlinklist_Get_Byvalue(dlinklist *h,data_t value)
{dlinklist *p = h->next;/* 遍历链表 */while(value != p->data){p = p->next;/* 若遍历完了 */if(p == h)return NULL;}if(p->data == value)return p;
}

7.在指定位置结点前插入新结点

/*** @description:            在指定位置的结点前插入一个新的结点* @param - h       :       要操作的链表的首结点指针* @param - pos     :       指定在哪个结点前插入* @param - value   :       要插入的结点的值* @return          :       0 为成功 ; 其他 为失败
*/
int Dlinklist_insert_before(dlinklist *h,int pos,int value)
{dlinklist *p,*q;p = Dlinklist_Get_Bypos(h,pos);if(NULL == p){return -1;}/* 创建一个新的结点 */q = (dlinklist *)malloc(sizeof(dlinklist));if(NULL == q){return -1;}q->data = value;q->prior = p->prior;q->next = p;p->prior->next = q;p->prior = q;return 0;
}

8.双向循环链表的删除

/*** @description:                指定序号，删除循环双链表中的结点* @param - h       :           要操作的链表的首结点指针* @param - pos     :           指定删除的结点的序号* @return          :           0 为成功 ; 其他为失败
*/
int Dlinklist_Delete_Bypos(dlinklist *h,int pos)
{dlinklist *p;p = Dlinklist_Get_Bypos(h,pos);/* 没找到指定序号的结点则退出，并返回错误信息 */if(NULL == p){return -1;}p->prior->next = p->next;p->next->prior = p->prior;free(p);return 0;
}

9.删除指定数值的结点

/*** @description:                指定序号，删除循环双链表中的结点* @param - h       :           要操作的链表的首结点指针* @param - pos     :           指定删除的结点的序号* @return          :           0 为成功 ; 其他为失败
*/
int Dlinklist_Delete_Bypos(dlinklist *h,int pos)
{dlinklist *p;/* 1.获取要删除的结点的指针 */p = Dlinklist_Get_Bypos(h,pos);/* 没找到指定序号的结点则退出，并返回错误信息 */if(NULL == p){return -1;}/* 2.删除指定的结点 p */p->prior->next = p->next;p->next->prior = p->prior;free(p);return 0;
}

10.倒置双向循环链表

/*** @description:                双向循环链表的倒置* @param - h       :           要操作的链表的首结点指针* @return          :           无
*/
void Dlinklist_Reverse(dlinklist *h)
{dlinklist *p,*q,*r;            //,r 指向首结点的下一个结点 a(0), p 指向当前要头插的结点，q 指向下一个结点，防止链表丢失/* 1.先把链表分成两部分 */r = h->next;p = r->next;h->prior = r;r->next = h;/* 从 a(1) 开始遍历 */while(p != h){/* 2.依次提取 a(1),a(2),a(3)... */q = p;p = p->next;/* 3.将 q 指向的结点，头插到 a(0) 前 */q->prior = h;q->next = r;h->next = q;r->prior = q;/* 4.将 r 指向 q 的结点 */r = q;}}

四.链表实战 - 使用单向循环链表实现 Joseph 问题

1.单链表的结构体定义

typedef int datatype;typedef struct node
{datatype data;         //数据域struct node *next;     //指向下一个结点的指针
}listnode;

2.使用键盘输入创建一个无 头结点 的循环单链表

/*** @description:                创建一个 Jeseph 单向循环链表* @param - n       :           要创建的结点数* @return          :           创建好的单向循环的第 0 个元素的指针     
*/
listnode *loop_list_create_init(int n)
{listnode *h,*r,*p;                      // h 指向第 0 个结点， r 指向当前循环链表的尾结点， p 指向新创建的结点int i = 0;                              //当前已经创建的结点数/* 指定创建的结点数不能 n <= 0 */while(0 >= n){printf("the number of the Joseph list must > 0 !\n");printf("input the number of Joseph:\n");scanf("%d",&n);}/* 1.创建第一个结点 */h = (listnode *)malloc(sizeof(listnode));if(NULL == h)return NULL;h->data = 1;h->next = h;/* 2.初始化 r 指向第一个结点 */r = h;/* 从第二个结点开始，循环创建 */for(i = 2;i <= n;i++){/* 2.创建新的结点 */p = (listnode *)malloc(sizeof(listnode));if(NULL == p)return NULL;/* 3.将新创建的结点插入尾部 */p->data = i;r->next = p;p->next = h;/* 4. r 指针向后移动，指向新加入的结点 */r = p;}return h;
}

3.按序号查找单向循环链表的结点

/*** @description:            按序号查找单向循环链表的结点* @param - h       :       要操作的单向循环链表的第一个元素的指针* @param - pos     :       要查找的结点的序号,输入的序号 : (0,1,2,3,4,5,......,n)
*/
listnode *Looplist_Get_Bypos(listnode *h,int pos)
{listnode *p;int i = 0;          //初始化为第 1 个结点if(0 > pos){printf("input pos is invalid!\n");return NULL;}/* 初始化 p 指向第一个结点 */p = h;/* 遍历单向循环链表 */while(i < pos){p = p->next;i++;#if 0   /* 若使能，则查找只能在一圈内查找 ， 不使能则可以循环查找 *//* 若遍历到尾结点了，还是没找到 */if(p->next == h)break;
#endif}/* 若找到了序号为 pos 的结点 */if(i == pos)return p;/* 没找到则返回 NULL */return NULL;
}

4. 用单向循环链表解决 Joseph 问题

/*** @description:            用无头结点的单向循环链表解决 Joseph 问题* @param - n       :       要创建的链表的结点个数* @param - k       :       约定的序号，即从哪个结点开始* @param - m       :       从约定的序号开始，第 m 个结点出列* @return          :       无
*/
void Joseph(int n,int k,int m)
{/* h 指向单向循环链表的第一个结点 ， p 指向序号为 k 结点 ，r 指向要出队的结点的前驱结点 ， q 指向要出队的结点 */listnode *h,*p,*r,*q;/* 1.创建一个 Joseph 链表 */h = loop_list_create_init(n);if(NULL == h){printf("loop_list_create_init failed!\n");return ;}/* 初始 p 结点指向头结点 */p = h;   /* 2.找到序号为 k 的结点 */p = Looplist_Get_Bypos(p,k-1);if(NULL == p){printf("input k is invalid!\n");return ;}                  while(p->next != p){/* 3.从结点 k 开始，找到要出队的结点的前驱结点 (m-1) */r = Looplist_Get_Bypos(p,m-1);/* 3. q 指向要出队的结点 */q = r->next;                // q = Looplist_Get_Bypos(p,m);p = q->next;/* 4. 结点 q 出队 */r->next = q->next;/* 5.打印出队的结点 */printf("%d",q->data);free(q);}printf("%d\n",p->data);}

5.最终代码测试

int main(int argc, char const *argv[])
{Joseph(6,1,3);return 0;
}