网站编辑可以做运营吗,发布外链,银川建设厅网站,如何做垂直网站我要成为嵌入式高手之3月20日数据结构第三天#xff01;#xff01; ————————————————————————————
双向链表 双向链表与单向链表的区别#xff1a;双向链表中的结点的指针域包含前驱结点的地址#xff0c;而单向链表的结点中指针域只有后驱结…我要成为嵌入式高手之3月20日数据结构第三天 ————————————————————————————
双向链表 双向链表与单向链表的区别双向链表中的结点的指针域包含前驱结点的地址而单向链表的结点中指针域只有后驱结点的地址。 双向链表操作前驱结点比单向链表方便单向链表若是要操作前驱结点就始终要用一个指针指向前驱结点否则很容易丢失前驱结点地址就要重新进行遍历。
1、创建链表 TWO_LIST *CreateLink()
{TWO_LIST *plist malloc(sizeof(TWO_LIST));if (NULL plist){perror(fail to malloc list);return NULL;}plist-phead NULL;plist-clen 0;return plist;
}2、创建结点 TWO_NODE *CreateNode(DATA_STU data)
{TWO_NODE *pnode malloc(sizeof(TWO_NODE));if (NULL pnode){perror(fail to malloc node);return NULL;}pnode-data data;pnode-ppre NULL;pnode-pnext NULL;return pnode;
}3、头插 int PushHeadNode(TWO_LIST *plist, TWO_NODE *pnode)
{if (pnode NULL || plist NULL){return -1;}if (plist-phead NULL){plist-phead pnode;}else{pnode-pnext plist-phead;plist-phead-ppre pnode;plist-phead pnode;}plist-clen;return 0;
}4、尾插 int PushTailNode(TWO_LIST *plist, TWO_NODE *pnode)
{TWO_NODE *ptmp NULL;if (pnode NULL || plist NULL){return -1;}if (plist-phead NULL){plist-phead pnode;}else{ptmp plist-phead;while (ptmp-pnext ! NULL){ptmp ptmp-pnext;}ptmp-pnext pnode;pnode-ppre ptmp;}plist-clen;return 0;
}5、从头遍历 int SearchHeadAll(TWO_LIST *plist)
{TWO_NODE *ptmp plist-phead;if (plist-phead NULL){printf(NO NODE!\n);return -1;}else{while (ptmp ! NULL){printf(StuInfo:\nid %d; name %s; score %d.\n, ptmp-data.id, ptmp-data.name, ptmp-data.score);ptmp ptmp-pnext;}}printf(len %d\n, plist-clen);return 0;
}6、从尾遍历 int SearchTailAll(TWO_LIST *plist)
{TWO_NODE *ptmp plist-phead;if (plist-phead NULL){printf(NO NODE!\n);return -1;}else{while (ptmp-pnext ! NULL){ptmp ptmp-pnext;}while (ptmp ! NULL){printf(StuInfo:\nid %d; name %s; score %d.\n, ptmp-data.id, ptmp-data.name, ptmp-data.score);ptmp ptmp-ppre;}}printf(len %d\n, plist-clen);return 0;
}7、查找 TWO_NODE *SearchInLink(TWO_LIST *plist, int id)
{TWO_NODE *dest plist-phead;while (dest ! NULL){if (dest-data.id ! id){dest dest-pnext;}else{return dest;}}return NULL;
}
8、修改 int ChangeInLink(TWO_LIST *plist, int uid, DATA_STU sdata)
{TWO_NODE *ptmp plist-phead;while (ptmp ! NULL){if (ptmp-data.id ! uid){ptmp ptmp-pnext;}else{ptmp-data sdata;return 1;}}return -1;
}9、头删 int PopHeadLink(TWO_LIST *plist)
{TWO_NODE *pfree plist-phead;if (NULL plist-phead){return -1;}else{pfree-pnext-ppre NULL;plist-phead pfree-pnext;free(pfree);plist-clen--;}return 0;
}10、尾删 int PopTailLink(TWO_LIST *plist)
{TWO_NODE *pfree plist-phead;if (NULL plist-phead){return -1;}else if (NULL plist-phead-pnext){free(pfree);}else{while (pfree-pnext ! NULL){pfree pfree-pnext;}pfree-ppre-pnext NULL;free(pfree);}plist-clen--;return 0;
}
11、销毁 int DestroyLink(TWO_LIST *plist)
{TWO_NODE *pfree NULL;TWO_NODE *ptmp plist-phead;if (NULL plist-phead){free(plist);}else{while (NULL ! ptmp){pfree ptmp;ptmp ptmp-pnext;plist-phead ptmp;free(pfree);}free(plist);}return 0;
}完整代码
头文件
#ifndef _LINK_H_
#define _LINK_H_#include stdio.h
#include stdlib.h/* 存储的数据类型 */
typedef struct stu
{int id;char name[32];int score;
}DATA_STU;/* 链表的结点类型 */
typedef struct node
{DATA_STU data; //数据域struct node *pnext; //后驱结点struct node *ppre; //前驱结点
}TWO_NODE;/* 描述链表属性的标签类型 */
typedef struct list
{TWO_NODE *phead; //存储头结点地址的指针int clen; //链表中当前结点个数
}TWO_LIST;extern TWO_LIST *CreateLink();
extern TWO_NODE *CreateNode(DATA_STU data);
extern int PushHeadNode(TWO_LIST *plist, TWO_NODE *pnode);
extern int SearchHeadAll(TWO_LIST *plist);
extern int SearchTailAll(TWO_LIST *plist);
extern int PushTailNode(TWO_LIST *plist, TWO_NODE *pnode);
extern TWO_NODE *SearchInLink(TWO_LIST *plist, int id);
extern int ChangeInLink(TWO_LIST *plist, int uid, DATA_STU sdata);
extern int PopHeadLink(TWO_LIST *plist);
extern int PopTailLink(TWO_LIST *plist);
extern int DestroyLink(TWO_LIST *plist);#endif功能函数文件
#include head.hTWO_LIST *CreateLink()
{TWO_LIST *plist malloc(sizeof(TWO_LIST));if (NULL plist){perror(fail to malloc list);return NULL;}plist-phead NULL;plist-clen 0;return plist;
}TWO_NODE *CreateNode(DATA_STU data)
{TWO_NODE *pnode malloc(sizeof(TWO_NODE));if (NULL pnode){perror(fail to malloc node);return NULL;}pnode-data data;pnode-ppre NULL;pnode-pnext NULL;return pnode;
}int PushHeadNode(TWO_LIST *plist, TWO_NODE *pnode)
{if (pnode NULL || plist NULL){return -1;}if (plist-phead NULL){plist-phead pnode;}else{pnode-pnext plist-phead;plist-phead-ppre pnode;plist-phead pnode;}plist-clen;return 0;
}int SearchHeadAll(TWO_LIST *plist)
{TWO_NODE *ptmp plist-phead;if (plist-phead NULL){printf(NO NODE!\n);return -1;}else{while (ptmp ! NULL){printf(StuInfo:\nid %d; name %s; score %d.\n, ptmp-data.id, ptmp-data.name, ptmp-data.score);ptmp ptmp-pnext;}}printf(len %d\n, plist-clen);return 0;
}int SearchTailAll(TWO_LIST *plist)
{TWO_NODE *ptmp plist-phead;if (plist-phead NULL){printf(NO NODE!\n);return -1;}else{while (ptmp-pnext ! NULL){ptmp ptmp-pnext;}while (ptmp ! NULL){printf(StuInfo:\nid %d; name %s; score %d.\n, ptmp-data.id, ptmp-data.name, ptmp-data.score);ptmp ptmp-ppre;}}printf(len %d\n, plist-clen);return 0;
}int PushTailNode(TWO_LIST *plist, TWO_NODE *pnode)
{TWO_NODE *ptmp NULL;if (pnode NULL || plist NULL){return -1;}if (plist-phead NULL){plist-phead pnode;}else{ptmp plist-phead;while (ptmp-pnext ! NULL){ptmp ptmp-pnext;}ptmp-pnext pnode;pnode-ppre ptmp;}plist-clen;return 0;
}TWO_NODE *SearchInLink(TWO_LIST *plist, int id)
{TWO_NODE *dest plist-phead;while (dest ! NULL){if (dest-data.id ! id){dest dest-pnext;}else{return dest;}}return NULL;
}int ChangeInLink(TWO_LIST *plist, int uid, DATA_STU sdata)
{TWO_NODE *ptmp plist-phead;while (ptmp ! NULL){if (ptmp-data.id ! uid){ptmp ptmp-pnext;}else{ptmp-data sdata;return 1;}}return -1;
}int PopHeadLink(TWO_LIST *plist)
{TWO_NODE *pfree plist-phead;if (NULL plist-phead){return -1;}else{pfree-pnext-ppre NULL;plist-phead pfree-pnext;free(pfree);plist-clen--;}return 0;
}int PopTailLink(TWO_LIST *plist)
{TWO_NODE *pfree plist-phead;if (NULL plist-phead){return -1;}else if (NULL plist-phead-pnext){free(pfree);}else{while (pfree-pnext ! NULL){pfree pfree-pnext;}pfree-ppre-pnext NULL;free(pfree);}plist-clen--;return 0;
}int DestroyLink(TWO_LIST *plist)
{TWO_NODE *pfree NULL;TWO_NODE *ptmp plist-phead;if (NULL plist-phead){free(plist);}else{while (NULL ! ptmp){pfree ptmp;ptmp ptmp-pnext;plist-phead ptmp;free(pfree);}free(plist);}return 0;
}主函数文件
#include head.hint main(void)
{TWO_LIST *plist NULL;TWO_NODE *pnode NULL;int i 0;int uid 0;/* 创建双向链表 */plist CreateLink();if (NULL plist){perror(fail to CreateLink);return -1;}/* 初始化要插入结点的数据 */DATA_STU data[5] {{1, zhangsan, 99},{2, lisi, 98},{3, wangwu, 97},{4, aaaaa, 96},{5, bbbbb, 95},};DATA_STU data1[5] {{6, zhangsan, 99},{7, lisi, 98},{8, wangwu, 97},{9, aaaaa, 96},{10, bbbbb, 95},};/* 创建头插结点并头插 */for (i 0; i 5; i){pnode CreateNode(data[i]);if (NULL pnode){perror(fail to CreateNode);return -1;}PushHeadNode(plist, pnode);}
#if 0/* 从头遍历、从尾遍历*/SearchHeadAll(plist);printf(\n);SearchTailAll(plist);printf(TAIL\n);
#endif/* 创建尾插结点并尾插 */for (i 0; i 5; i){pnode CreateNode(data1[i]);if (NULL pnode){perror(fail to CreateNode);return -1;}PushTailNode(plist, pnode);}
#if 0/* 双向遍历 */SearchHeadAll(plist);printf(\n);SearchTailAll(plist);
#endif
#if 0/* 查找对应id号的学生信息 */printf(\n);printf(Input stu id to search:\n);scanf(%d, uid);TWO_NODE *dest SearchInLink(plist, uid);if (NULL dest){printf(NO STUDENT!\n);}else{printf(The Dest StuInfo:\nid %d; name %s; score %d.\n, dest-data.id, dest-data.name, dest-data.score);}#endif#if 0/* 修改对应id号的学生信息 */DATA_STU sdata {0};printf(\n);printf(Input stu id to change:\n);scanf(%d, sdata.id);printf(Input stu info to change:\nname:);scanf(%s, sdata.name);printf(score:);scanf(%d, sdata.score);putchar(\n);ChangeInLink(plist, sdata.id, sdata);SearchHeadAll(plist);
#endif
#if 0/* 头删 */SearchHeadAll(plist);printf(\n);PopHeadLink(plist);SearchHeadAll(plist);
#endif
#if 0/* 尾删 */SearchHeadAll(plist);printf(\n);PopTailLink(plist);PopTailLink(plist);PopTailLink(plist);PopTailLink(plist);SearchHeadAll(plist);
#endif
#if 1/* 销毁 */SearchHeadAll(plist);printf(\n);SearchTailAll(plist);DestroyLink(plist);#endifreturn 0;
}Makefile文件
all:doulinkdoulink:main.c twolink.cgcc $^ -o $.PHONY:
clean:rm doulink;
作业
12、删除双向链表指定结点
int DeleteIdNode(TWO_LIST *plist, int uid)
{TWO_NODE *dest plist-phead;while (dest ! NULL){if (dest-data.id ! uid){dest dest-pnext;}else{dest-ppre-pnext dest-pnext;dest-pnext-ppre dest-ppre;free(dest);plist-clen--;}}return 0;
} 13、双向链表倒置
int ReverseTwoLink(TWO_LIST *plist)
{TWO_NODE *ptmp plist-phead;TWO_NODE *pver NULL;struct node *p NULL;if (plist-phead NULL || plist-phead-pnext NULL){return -1;}while (ptmp-pnext ! NULL){ptmp ptmp-pnext;}plist-phead ptmp;while (ptmp ! NULL){pver ptmp;ptmp ptmp-ppre;p pver-pnext;pver-pnext pver-ppre;pver-ppre p;}return 0;
}
