郝斌数据结构1线性表

浅浅的花香味﹌ 2022-03-02 05:28 219阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70]  
一. 连续存储–>数组  
数组的增删改查程序

#include <stdio.h>
    #include <stdlib.h>
    
    #define N 100
    typedef int datatype; // typedef有分号！！
    //这样如果想定义char型数组，就把int改成char就行了
    typedef struct
    { 
    	datatype data[N];
    	int last; //last存放[最后]一个元素的下标
    } sqlist; //定义了sqlist的结构体类型
    
    sqlist * list_create();
    int list_insert(sqlist *L, datatype value);
    int list_insert_pos(sqlist *L, datatype value, int pos);
    int list_full(sqlist *L);
    // 1-------满 0-------不满
    int list_empty(sqlist *L);
    // 1-------空 0-------非空
    int list_delete(sqlist *L);
    int list_delete_pos(sqlist *L, int pos);
    void list_show(sqlist *L);
    int list_replace(sqlist *L, datatype value, int pos);
    int list_replace_value(sqlist *L, datatype old, datatype new);
    int list_search(sqlist *L, datatype value);
    //找到-----1 找不到------0
    void list_purge(sqlist *L);
    void list_union(sqlist *La, sqlist *Lb);
    
    int main(void)
    { 
    	sqlist *L = NULL;
    	sqlist *La = NULL;
    	sqlist *Lb = NULL;
    	int search;
    
    	if (NULL == (L = list_create()))
    	{ //create函数失败的返回值是NULL
    		//这里将L指向动态存储区,注意(L = list_create())要打上括号，否则
    		//"=="的优先级高于"=",语句会出错
    		printf("list_create failed\n");
    		return -1;
    	}
    
    	if ((La = list_create()) == NULL) //create函数失败返回值是NULL
    	{ //这里将La指向动态存储区
    		printf("list_create failed\n");
    		return -1;
    	}
    
    	if ((Lb = list_create()) == NULL) //create函数失败返回值是NULL
    	{ //这里将Lb指向动态存储区
    		printf("list_create failed\n");
    		return -1;
    	}
    
    	list_insert(L, 5);
    	list_insert(L, 6);
    	list_insert(L, 1);
    	list_insert(L, 4);
    	list_insert(L, 8);
    	list_insert(L, 8);
    	list_insert(L, 9);
    	list_insert(L, 9);
    	list_show(L);
    
    	list_insert_pos(L, 111, 0);
    	list_insert_pos(L, 222, 5);
    	list_insert_pos(L, 333, 20);
    	list_show(L);
    
    	list_delete(L);
    	list_delete(L);
    	list_show(L);
    
    	list_delete_pos(L, 5);
    	list_delete_pos(L, 31);
    	list_show(L);
    
    	list_purge(L);
    	list_show(L);
    
    	list_replace(L, 13, 2);
    	list_replace(L, 14, 3);
    	list_show(L);
    
    	list_replace_value(L, 13, 100);
    	list_replace_value(L, 1, 100);
    	list_show(L);
    
    	search = list_search(L,5);
    	printf("%d\n", search);
    	search = list_search(L,999);
    	printf("%d\n", search);
    
    	list_insert(La, 1);
    	list_insert(La, 2);
    	list_insert(La, 3);
    	list_insert(La, 4);
    	list_insert(Lb, 5);
    	list_insert(Lb, 6);
    	list_insert(Lb, 7);
    
    	list_union(La, Lb);
    
    	free(L);
    	free(La);
    	free(Lb);
    
    	return 0;
    }
    
    sqlist *list_create()
    { 
    	sqlist *L = NULL;
    
    	L = malloc(sizeof(sqlist));
    	//malloc前可以不加类型转换了，自动转换
    
    	if (NULL == L)
    	{ //申请不上那L没指向新空间还指向NULL
    		printf("malloc failed\n");
    		return NULL;//返回值也是NULL
    	}
    
    	L->last = -1;
    	//数组元素从0开始，有一个元素时last是0，没有时是-1
    	return L;
    }
    
    int list_insert(sqlist *L, datatype value)
    { //在表的末尾插入
    	if (list_full(L))
    	{ 
    		printf("list is full!\n");
    		return -1;
    	}
    
    	L->data[L->last + 1] = value;
    	L->last++;
    	return 0;
    }
    
    int list_full(sqlist *L)
    { //判断表的空间是不是满了
    	return L->last == (N - 1) ? 1 : 0;
    }//定义N个元素，下标就是0到N-1
    
    int list_empty(sqlist *L)
    { 
    	return L->last == -1;
    }
    
    void list_show(sqlist *L)
    { 
    	int i;
    	for (i = 0; i <= L->last; i++)
    	{ 
    		printf("%d ", L->data[i]);
    	}
    	putchar(10);
    	return;
    }
    
    int list_insert_pos(sqlist *L, datatype value, int pos)
    { //在表的任意位置插入
    	int i;
    	if (list_full(L))
    	{ 
    		printf("list is full!\n");
    		return -1;
    	}
    
    	if (pos < 0 || pos > L->last + 1)//要保证插入后位置是连续的
    	{ //不是>=,可以在last也就是最后一个位置上面插入，仍然是连续的
    		printf("error pos\n");
    		return -1;
    	}
    
    	for (i = L->last; i >= pos; i--)
    	{ //在pos处插入，要把pos处原值及以上值全部上移，空出pos位置
    		L->data[i + 1] = L->data[i];
    	}
    
    	L->data[pos] = value;//把值插在pos空位
    	L->last++;
    
    	return 0;
    }
    
    int list_delete(sqlist *L) //删除末尾
    { 
    	if (list_empty(L))
    	{ //empty空了返回1，if是真
    		printf("list is empty\n");
    		return -1;
    	}
    
    	L->last--;//多的那个数等着被覆盖就行了
    	return 0;
    }
    
    int list_delete_pos(sqlist *L, int pos)
    { //删除任意位置元素
    	int i;
    	if (list_empty(L))
    	{ 
    		printf("list is empty\n");
    		return -1;
    	}
    
    	if (pos < 0 || pos > L->last)
    	{ 
    		printf("error pos\n");
    		return -1;
    	}
    
    	for (i = pos; i < L->last; i++)
    	{ //i是<,因为下面是data[i+1],执行到last前一个就把
    		//last值给它了。因为元素数少了1个，最后last值没意义，
    		//加上等号多走一步当然没有错误
    		L->data[i] = L->data[i + 1];
    	}//删除pos，就把pos以上的元素依次往下覆盖就行
    
    	L->last--;
    	return 0;
    }
    
    int list_replace(sqlist *L, datatype value, int pos)
    { //替换任意位置元素
    	if (list_empty(L))
    	{ 
    		printf("list is empty\n");
    		return -1;
    	}
    
    	if (pos < 0 || pos > L->last)
    	{ 
    		printf("error pos\n");
    		return -1;
    	}
    
    	L->data[pos] = value;
    	return 0;
    }
    
    int list_replace_value(sqlist *L, datatype old, datatype new)
    { //替换某个具体数值
    	int i;
    	for (i = 0; i <= L->last; i++)
    	{ 
    		if (L->data[i] == old)
    		{ 
    			L->data[i] = new;
    			return 0;
    		}
    	}
    
    	printf("no found old\n");
    	return -1;
    }
    
    int list_search(sqlist *L, datatype value)
    { //查找
    	int i;
    	for (i = 0; i <= L->last; i++)
    	{ 
    		if (L->data[i] == value)
    		{ 
    			return 1;
    		}
    	}
    
    	return 0;
    }
    
    void list_purge(sqlist *L)
    { //清除相同的元素
    	int i, j;
    	for (i = 0; i < L->last; i++)
    	{ //因为下面是j=i+1,所以<
    		for (j = i + 1; j <= L->last; j++)
    		{ 
    			if (L->data[i] == L->data[j])
    			{ 
    				list_delete_pos(L, j);
    				j--;
    			}
    		}
    	}
    }
    
    /* j--解析：如果元素是1[2]34[2]567，那么检测到两个2相同，就把后面那个2删去， 也就是567往前覆盖。没有没有j--，j++就到了6的位置，那么5被忽视了。 */
    
    void list_union(sqlist *La, sqlist *Lb)
    { //将数组b添加到数组a的后面
    	int i;
    	for (i = 0; i <= Lb->last; i++)
    	{ 
    		La->data[La->last + 1] = Lb->data[i];
    		La->last++;
    	}
    
    	list_show(La);
    	printf("L->last = %d\n", La->last);
    }
    
    /*list_union方法2 void list_union(sqlist *La,sqlist *Lb) { int i; for (i = 0;i <= Lb->last;i++) { La->data[La->last+1+i] = Lb->data[i]; } La->last = La->last + Lb->last + 1; //数组b有10个数，Lb->last为9，所以最后加1 list_show(La); printf("La->last = %d\n",La->last); } */

运行结果:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70 1]  
二. 离散存储–>链表

1.  链表的定义  
    n个节点离散分配，彼此通过指针相连，每个节点只有1个后续节点，第一个节点没有前驱  
    节点，尾节点没有后续节点。
2.  专业术语：  
    首节点：第一个有效节点  
    尾节点：最后一个有效节点  
    头节点：头节点是第一个有效节点之前的那个节点，头节点并不存放有效数据，也没有存放  
    链表中有效节点的个数。加头节点的目主要是为了方便对链表的操作  
    链表为空时就是里面只有一个头结点，不是什么都没有！
    
    头指针：指向头节点的指针变量  
    尾指针：指向尾节点的指针变量
3.  如果希望通过一个函数来对链表进行处理，我们至少需要接受链表的哪些参数  
    只需要一个参数：头指针  
    因为我们通过头指针可以推算出链表的其他所有参数
4.  每一个链表节点的数据类型该如何表示

typedef struct Node
    { 
    	int data;  //数据域
    	struct Node * pNext;  //指针域
    }NODE, *PNODE;
    //NODE等价于struct Node，PNODE等价于struct Node *！！！

![在这里插入图片描述][20190319193904543.png]  
5. 链表的分类  
单链表：每个链表的指针域只能指向后面的节点  
双链表：每一个节点有两个指针域  
循环链表：能通过任何一个节点找到其他所有的结点  
非循环链表：  
6. 非循环单链表插入节点图解  
![在这里插入图片描述][20190319193954522.png]  
插入算法1 推荐 q->Next=p->pNext; p->Next=q;  
注意: p，q不是节点，是指针变量！这两行的顺序不能倒过来！  
插入算法2 r=p->pNext; p->Next=q; q->pNext=r;

1.  删除非循环单链表节点图解  
    算法1（不采用）：  
    ![在这里插入图片描述][20190319194206979.png]  
    p->pNext=p->pNext->pNext; //代码是A步骤，把第2个节点的指向给了第1个节点的指向  
    //经过A步骤就实现了B步骤
    
    为什么不行:  
    如图，这样做了之后指向第2个节点的指针就没了，就是说我就找不到第2个节点了。这样  
    我就没有释放第2个节点的内存了！

算法2：算法1加一步即可，先临时定义一个指向p后面节点的指针r  
r=p->pNext;  
p->pNext=p->pNext->pNext;  
free®;

1.  链表的反转(华三笔试题)  
    用头插法来创建链表，插入的顺序是123456，但是输出的顺序就是654321，  
    现在的挑战是怎么让输入和输出的顺序一致？

void list_reverse(linklist *H)
    { 
    	linklist *p = H->next,*q = NULL;
    	H->next = NULL;
    
    	while(p != NULL)
    	{ 
    		q = p;
    		p = p->next;
    		q->next = H->next;
    		H->next = q;
    	}
    	}

解析:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70 3]  
9. 程序如下:

#include <stdio.h>
    #include <malloc.h>
    
    typedef int datatype;
    
    struct node
    { 
    	datatype data;
    	struct node * next;
    };
    
    typedef struct node linklist;
    
    linklist * list_create();
    int head_insert(linklist *H,datatype value);
    int head_delete(linklist *H);
    void list_show(linklist *H);
    int list_empty(linklist *H);
    int list_insert_pos(linklist *H,datatype value,int pos);
    int list_delete_value(linklist *H,datatype value);
    int list_replace(linklist *H,datatype old,datatype new);
    int list_search(linklist *H,datatype value);
    void list_reverse(linklist *H);
    
    int main(void)
    { 
    	linklist * H = NULL;
    
    	if (NULL == (H = list_create()))
    	{ 
    		printf("list_create failes\n");
    		return -1;
    	}
    
    	printf("没有反转输出如下:\n");
    	head_insert(H,1);
    	head_insert(H,2);
    	head_insert(H,3);
    	head_insert(H,4);
    	head_insert(H,5);
    	head_insert(H,6);
    	list_show(H);
    
    	printf("头插入如下:\n");
    	head_insert(H,111);
    	head_insert(H,222);
    	list_show(H);
    
    	printf("任意合法位置插入如下:\n");
    	list_insert_pos(H,333,0);
    	list_insert_pos(H,555,2);
    	list_show(H);
    
    	printf("头删如下:\n");
    	head_delete(H);
    	list_show(H);
    
    	printf("删除具体值如下:\n");
    	list_delete_value(H,6);
    	list_delete_value(H,10);
    	list_show(H);
    
    	printf("替换如下:\n");
    	list_replace(H,5,20);
    	list_show(H);
    	list_replace(H,100,20);
    	list_show(H);
    
    	printf("查找如下:\n");
    	printf("pos:%d\n",list_search(H,555));
    	printf("pos:%d\n",list_search(H,100));
    
    	printf("反转输出如下:\n");
    	list_reverse(H);
    	list_show(H);
    
    	return 0;
    }
    
    linklist *list_create()
    { //(H = malloc(sizeof(linklist))别忘了打括号
    	//因为“==”优先级高于“=”，不打括号语句错误
    	linklist * H = NULL;
    	if (NULL == (H = malloc(sizeof(linklist))))
    	{ 
    		printf("malloc failed\n");
    		return NULL;
    	}
    
    	H->next = NULL;
    
    	return H;
    }
    
    int head_insert(linklist *H, datatype value)
    { //在头结点的后面插入
    	linklist * p = NULL;
    	if (NULL == (p = malloc(sizeof(linklist))))
    	{ //p指向要插入的元素的空间
    		printf("malloc failed\n");
    		return -1;
    	}
    
    	p->data = value;
    	p->next = H->next;
    	H->next = p;
    
    	return 0;
    }
    
    void list_show(linklist * H)
    { 
    	while (H->next != NULL)
    	{ 
    		printf("%d ", H->next->data);//注意是H->next->data!!!
    		//头结点不存放内容，所以是输出下一个的内容!!!
    		H = H->next;
    		//指向头结点的指针不断移向下一个，当H指向的节点中的next指针指向
    		//NULL时，就没有下一个内容可以输出了。H指向尾时，上一次已经把尾的
    		//内容输出了
    	}
    
    	putchar(10);
    }
    
    int list_empty(linklist * H)
    { //1是空 0是非空
    	if (H->next != NULL)
    	{ 
    		return 0;
    	}
    
    	else
    	{ 
    		return 1;
    	}
    }
    
    int head_delete(linklist * H)
    { //头删，删除头结点后面的那个，直接把头结点指向后面的后面那个
    	//再把头结点后面的释放
    	if (list_empty(H))
    	{ 
    		printf("list is empty\n");
    		return -1;
    	}
    
    	linklist * p = H->next;
    	H->next = p->next;
    	free(p);
    	p = NULL;//防止野指针！！
    
    	return 0;
    }
    
    int list_insert_pos(linklist * H, datatype value, int pos)
    { //在任意合法位置插入
    	/*原理:头节点之后的首节点及以后的位置分别为0,1,2,3...注意头结点不算位置! * 0位置是首节点! 我想在3处插入，pos = 3,那我将头指针移动到2处， * 然后就是在头结点的后面插入*/
    
    	int i = 0;//注意i从0开始
    	linklist * p = H, *q = NULL; //p是头指针，q指向pos
    
    	while (i < pos && p != NULL)
    	{ 
    		p = p->next;
    		i++;
    	}
    
    	/*正确情况下，有0-5个位置，pos=3,那我要将p指向位置2。 * i = 0时p指向0位置，i++,i=1; * 1 = 1时p指向1位置，i++,i=2; * 1 = 2时p指向2位置，i++,i=3,不满足小于pos，退出循环; * 再往后就是头插法了 * *如果要在0位置插入，pos = 0,不满足循环条件直接执行下面的头插法代码 * *错误情况: 有0-5个位置,5里指针指向NULL,我最大可以在6处插入，我将p指向5 *但是我在7,8,9...处插入就错误了，假设我pos = 7 *i=5时p指向5， i++,i=6; *i=6时p指向NULL， i++,i=7退出循环; *往下执行头插法代码时，p指向NULL了，p->next就错误了! *所以while循环里要求p != NULL,就是用来限制pos不能超过6的！ */
    
    	if (NULL == p)
    	{ 
    		printf("error pos\n");
    		return -1;
    	}
    
    	if (NULL == (q = malloc(sizeof(linklist))))
    	{ 
    		printf("malloc failed\n");
    		return -1;
    	}
    
    	//下面就是同在头结点后面插入
    	q->data = value;
    	q->next = p->next;
    	p->next = q;
    
    	return 0;
    }
    
    int list_delete_value(linklist *H,datatype value)
    { //查找并删除某个确定值
    	linklist * p = H,* q = NULL;//q指向要删除的位置
    	while(p->next != NULL)
    	{ //第1次循环排除空链表的情况
    		if (value == p->next->data)
    		{ //头节点不放内容，所以从下一个开始找!
    			q = p->next;//要删除的位置给q
    			p->next = q->next;//把q指向的下一个交给p，这样q就没用了
    
    			free(q);
    			q = NULL;//预防野指针
    
    			return 0;
    		}
    
    		else
    			p = p->next;
    //p一步步往下走直到指向尾节点时就跳出循环了,p指向尾巴时上一次已经判断尾巴里的内容了
    	}
    
    	printf("no value\n");
    	return -1;
    
    }
    
    int list_replace(linklist * H,datatype old,datatype new)
    { 
    	linklist * p = H;
    	while(p->next != NULL)
    	{ 
    		if (p->next->data == old)
    		{ 
    			p->next->data = new;
    			return 0;
    		}
    		else
    		{ 
    			p = p->next;
    		}
    	}
    
    	printf("no old\n");
    	return -1;
    }
    
    int list_search(linklist * H,datatype value)
    { 
    	int pos = 0;
    	linklist * p = H;
    	while(p->next != NULL)
    	{ 
    		if (value == p->next->data)
    		{ 
    			return pos;
    		}
    
    		else
    		{ 
    			p = p->next;
    			pos++;
    		}
    	}
    
    	return -1;
    }
    
    void list_reverse(linklist *H) //链表的反转
    { //输入123456，输出是654321，我们要让输入输出一样
    	linklist * p = H->next,* q = NULL;
    	H->next = NULL;
    	while(p != NULL)
    	{ 
    		q = p;
    		p = p->next;
    		q->next = H->next;
    		H->next = q;
    	}
    }
    /*统计节点中最大值，最小值和累加值，自己写的，华三笔试题*/
    void statistic(linklist *H) 
    { 
    	datatype Min,Max,t,Total = 0;
    	Min = Max = H->next->data;
    
    	while(H->next != NULL)
    	{ 
    		t = H->next->data; 
    		if (t > Max)
    		{ 
    			Max = t;
    		}
    
    		if (t < Min)
    		{ 
    			Min = t;
    		} 
    		H = H->next;
    		Total = Total + t;
    	}
    	printf("Min = %d,Max = %d,Total = %d\n",Min,Max,Total);
    }

运行结果如图:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70 4]  
10. 小算法: 如果两个链表la,lb本身已经从小到大排好序，要求将lb插入la的后面，然后从小到大排好序输出。注意: 前提是la,lb本身已经从小到大排好了！

#include<stdio.h>
    		#include<stdlib.h>
    		typedef int datatype;
    struct node
    { 
    	datatype data;
    	struct node * next;
    };
    
    typedef struct node linknode;
    
    linknode * list_create();
    int head_insert(linknode * H,datatype value);
    void show(linknode *H);
    void Merge(linknode *Ha,linknode *Hb);
    
    int main()
    { 
    	linknode * ha = NULL, *hb = NULL;
    	if ((ha = list_create()) == NULL)
    	{ 
    		printf("create list failed\n");
    		return -1;
    	}
    	if ((hb = list_create()) == NULL)
    	{ 
    		printf("create list failed\n");
    		return -1;
    	}
    //要求两个链表本身已经是从小到大输出，这个前提要满足!
    	//另外从小到大输出，那就要从大到小输入!
    	head_insert(ha, 60);
    	head_insert(ha, 50);
    
    	head_insert(hb, 70);
    	head_insert(hb, 60);
    	head_insert(hb, 3);
    
    	show(ha);
    	show(hb);
    	Merge(ha, hb);
    	show(ha);
    
    	return 0;
    }
    
    linknode *list_create()
    { 
    	linknode * h = NULL;//头指针
    
    	if ((h = malloc(sizeof(linknode))) == NULL)
    	{ 
    		printf("malloc failed\n");
    		return NULL;
    	}
    
    	h->next = NULL;
    
    	return h;
    }
    
    int head_insert(linknode * h, datatype value)
    { 
    	linknode *p = NULL;
    	if ((p = malloc(sizeof(linknode))) == NULL)
    	{ 
    		printf("malloc node failed\n");
    		return -1;
    	}
    
    	p->data = value;
    	p->next = h->next;
    	h->next = p;
    
    	return 0;
    }
    
    void show(linknode *h)
    { 
    	while (h->next != NULL)
    	{ 
    		printf("%d ", h->next->data);
    		h = h->next;
    	}
    	putchar(10);
    }
    
    void Merge(linknode * ha, linknode *hb)
    { 
    	linknode * p = ha->next, *q = hb->next, *r = ha;
    	free(hb);
    //hb插入ha的后面，hb的头结点就不需要了,这一步别忽略了!
    	while (p && q)
    	{ 
    		if (p->data <= q->data)
    		{ 
    			r->next = p;
    			r = p;
    			p = p->next;
    		}
    		else
    		{ 
    			r->next = q;
    			r = q;
    			q = q->next;
    		}
    	}
    
    	if (NULL == p)
    	{ 
    		p = q;
    	}
    
    	r->next = p;
    }

解析1: ha的节点数少于hb的情况  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70 5]  
解析2: ha的节点数多于hb的情况  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70 6]  
11. 什么是泛型  
狭义的算法是与数据的存储方式密切相关  
广义的算法是与数据的存储方式无关  
泛型：  
同一种逻辑结构，无论该逻辑结构物理存储是什么样子的，我们可以对它执行相同的操作。

1.  数组和链表的优缺点比较  
    数组优点: 存取速度很快  
    数组缺点:  
    事先需要知道数组的长度  
    插入删除元素很慢  
    空间通常有限制  
    需要大块连续的内存块  
    链表优点:  
    空间没有限制  
    插入删除元素很快  
    链表缺点:  
    存取速度很慢
    
    三. 双向循环链表

#include <stdio.h>
    #include <stdlib.h>
    
    typedef int datatype;
    typedef struct node
    { 
    	datatype data;
    	struct node *next;
    	struct node *prior;
    } linklist;
    
    linklist * list_create();
    int list_insert(linklist *H, datatype value);
    int list_delete(linklist *H);
    void list_show(linklist *H);
    
    int main(void)
    { 
    	linklist *H = NULL;
    
    	if ((H = list_create()) == NULL)
    	{ 
    		printf("list_create failed\n");
    		return -1;
    	}
    
    	list_insert(H, 2);
    	list_insert(H, 3);
    	list_insert(H, 4);
    	list_insert(H, 5);
    	list_show(H);
    
    	list_delete(H);
    	list_show(H);
    	list_delete(H);
    	list_show(H);
    	return 0;
    }
    
    linklist *list_create()
    { 
    	linklist *H = NULL;
    	if (NULL == (H = malloc(sizeof(linklist))))
    	{ 
    		printf("malloc failed\n");
    		return NULL;
    	}
    
    	H->data = 1;//这里头结点就不是不存数据了!!
    	H->next = H;
    	H->prior = H;
    
    	return H;
    }
    
    int list_insert(linklist *H, datatype value)
    { //头插，插在头结点的后面。看笔记的解析，画个图就清楚了
    	linklist *p = NULL;
    	if ((p = malloc(sizeof(linklist))) == NULL)
    	{ 
    		printf("malloc failed\n");
    		return -1;
    	}
    
    	p->data = value;
    	p->next = H->next;
    	p->next->prior = p;
    	H->next = p;
    	p->prior = H;
    
    	return 0;
    }
    
    void list_show(linklist *H)
    { 
    	linklist *p = H;
    	while (p->next != H)
    	{ //如图，如果只有一个节点p->next指向H，这时候不用循环，直接把这个
    		//节点的值输出就行了。若不是一个节点，进入循环，当p->next再次指向H时
    		//就证明链表遍历一次结束了，这时候就退出循环，把H指向的前一个节点值输出就行了
    		//这样就从H节点值开始，遍历一圈，到H前一个节点值结束
    		printf("%d ", p->data);
    		p = p->next;
    	}
    
    	printf("%d\n", p->data);
    }
    
    int list_delete(linklist *H)
    { //删除H->next指向的节点，看笔记解析，画个图就明白了
    	linklist *p = H->next;
    	H->next = p->next;
    	p->next->prior = H;
    
    	free(p);
    	p = NULL;
    }

程序解析:  
插入函数解析  
![在这里插入图片描述][20190319194955876.png]  
![在这里插入图片描述][20190319195006953.png]  
![在这里插入图片描述][20190319195019280.png]  
删除函数解析:  
![在这里插入图片描述][20190319195046458.png]  
![在这里插入图片描述][20190319195055987.png]  
![在这里插入图片描述][20190319195105218.png]

1.  华三笔试题  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70 7]  
    解:  
    ![在这里插入图片描述][20190319195202162.png]

NODE_S  *ReGroup（NODE_S  *pstSep ）
    { 
    	NODE_S  *pstHead = pstSep->pstPrev->pstPrev;
    	NODE_S  *pstTail = pstSep->->pstNext->pstNext->pstNext;
    	
    	//先假设截断，将AB加到F的后面
    	pstHead-> pstPrev = pstTail;
    	pstTail-> pstNext = pstHead;
    	
    	//截断
    	pstSep-> pstPrev->pstNext = NULL;
    	pstSep-> pstPrev = NULL;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70]: /images/20220302/21fa6ac88f8243a48044e60edf84784b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70 1]: /images/20220302/aa07310895ae474584462341eebabb7e.png
[20190319193904543.png]: /images/20220302/79a624bc4cc34cc489c9ed970479b330.png
[20190319193954522.png]: /images/20220302/d10d0d9278a248b0949916fcddfee5af.png
[20190319194206979.png]: /images/20220302/a2e5587f88b9443ca67f5f280344db75.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70 2]: /images/20220302/a7ea2fe7065f4e8b819e1e93b1392512.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70 3]: /images/20220302/60876e0dbc67432ab101b0b6c611855a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70 4]: /images/20220302/d5f957b22e994d4ab910eca43de004d3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70 5]: /images/20220302/eded81f088c1455bbf35ed2b4b643726.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70 6]: /images/20220302/45b8343a040f4aa59e23554e765afe1d.png
[20190319194955876.png]: /images/20220302/d5003b194f384ffdba1356819c78011e.png
[20190319195006953.png]: /images/20220302/ede223a3b61b459eb78e30fe244a76af.png
[20190319195019280.png]: /images/20220302/cd83345da7e04e1f86559861559dd677.png
[20190319195046458.png]: /images/20220302/a8b60e3decaf4e42b2d43d802386c65a.png
[20190319195055987.png]: /images/20220302/e0c741babc3d4415a0de9818def36a89.png
[20190319195105218.png]: /images/20220302/9d862fd0ba314b0b9c836fbc1e20a398.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70 7]: /images/20220302/f93a59bed9b04796b984b22c07e075ad.png
[20190319195202162.png]: /images/20220302/0f41130dcc1d48c583f2c4b731f424b3.png