/* 项目名称:双向链表的基本操作
* 项目功能:
* 创建链表、遍历(打印)、求长度、排序、插入、删除、查找
*
* 项目总结:
*
* */
测试代码:
- #include <stdio.h>
- #include <stdlib.h>
-
- typedef struct Node
- {
- int data;
- struct Node * next;
- struct Node * prior;
- }NODE, *PNODE;
-
- PNODE create_list(void);
- void traverse_list(PNODE pHead);
- int length_list(PNODE pHead);
- void sort_list(PNODE pHead);
- void insert_list(PNODE pHead, int pos, int val);
- void delect_list(PNODE pHead, int pos, int *val);
- int find_list(PNODE pHead, int val,int *pos);
-
- int main(int argc, char* argv[])
- {
- int pos_insert;
- int val_insert;
- int pos_delect;
- int val_delect;
- int pos_find;
- int val_find;
-
- PNODE pHead = NULL;
-
- pHead = create_list();
- printf("/n原来链表:/n");
- traverse_list(pHead);
- printf("链表的长度是:%d/n",length_list(pHead));
- printf("/n");
-
- printf("请输入您要插入的元素位置:pos = ");
- scanf("%d",&pos_insert);
- printf("请输入您要插入的元素值:val = ");
- scanf("%d",&val_insert);
- printf("插入元素后:/n");
- insert_list(pHead, pos_insert, val_insert);
- traverse_list(pHead);
- printf("链表的长度是:%d/n",length_list(pHead));
- printf("/n");
-
- printf("请输入您要删除的元素位置:pos = ");
- scanf("%d",&pos_delect);
- printf("删除元素后:/n");
- delect_list(pHead, pos_delect, &val_delect);
- traverse_list(pHead);
- printf("链表的长度是:%d/n",length_list(pHead));
- printf("您删除的节点元素是:%d/n",val_delect);
- printf("/n");
-
- printf("请输入您要查找的元素的值:val = ");
- scanf("%d",&val_find);
- printf("查找元素:/n");
- if(find_list(pHead, val_find, &pos_find) == 0)
- {
- traverse_list(pHead);
- printf("您要查找的元素位置是:%d/n", pos_find);
- printf("/n");
- }
- else
- printf("您要查找的元素不存在!/n");
- printf("/n");
-
- printf("排序后:/n");
- sort_list(pHead);
- traverse_list(pHead);
- printf("链表的长度是:%d/n",length_list(pHead));
- printf("/n");
-
- return 0;
- }
链表代码:
- PNODE create_list(void)
- {
- int len;
- int i, val;
- PNODE pTail;
-
- PNODE pHead = (PNODE)malloc(sizeof(NODE));
- if(NULL == pHead)
- {
- printf("动态内存分配失败,程序终止!/n");
- exit(-1);
- }
- pTail = pHead;
- pTail->next = NULL;
-
- printf("请输入您要创建链表的长度:/nlen = ");
- scanf("%d",&len);
-
- for(i = 0; i < len; i++)
- {
- printf("请输入第%d个节点的值:val = ", i+1);
- scanf("%d",&val);
-
- PNODE pNew = (PNODE)malloc(sizeof(NODE));
- if(NULL == pNew)
- {
- printf("新节点动态内存分配失败,程序终止!/n");
- exit(-1);
- }
- pNew->data = val;
- pTail->next = pNew;
- pNew->prior = pTail; //更正错误
- pNew->next = NULL;
- pTail = pNew;
- }
- return pHead;
- }
-
- void traverse_list(PNODE pHead)
- {
- PNODE p;
- p = pHead->next;
- if(NULL == p)
- {
- printf("链表为空!/n");
- }
- while(NULL != p)
- {
- printf("%d ",p->data);
- p = p->next;
- }
- printf("/n");
-
- return;
- }
-
- int length_list(PNODE pHead)
- {
- int len = 0;
- PNODE p;
- p = pHead;
-
- while(NULL != p)
- {
- len++;
- p = p->next;
- }
- return len-1;
-
- }
-
- void sort_list(PNODE pHead)
- {
- int len, i, j, temp;
- PNODE p, q;
-
- len = length_list(pHead);
-
- for(i = 0,p = pHead->next; i < len; i++,p = p->next)
- {
- for(j = i+1, q = p->next; j < len; j++, q = q->next)
- {
- if(p->data > q->data)
- {
- temp = p->data;
- p->data = q->data;
- q->data = temp;
- }
- }
- }
- return;
- }
-
- void insert_list(PNODE pHead, int pos, int val)
- {
- int i;
- PNODE pNew, p;
- p = pHead;
-
- pNew = (PNODE)malloc(sizeof(NODE));
- if(NULL == pNew)
- {
- printf("新节点动态内存分配失败,程序终止!/n");
- exit(-1);
- }
- pNew->data = val;
-
- if((pos > (length_list(pHead)+1)) || (pos <= 0))
- {
- printf("插入失败,插入位置不正确!/n");
- exit(-1);
- }
- for(i = 0; i < pos-1; i++)
- {
- p = p->next;
- }
- pNew->next = p->next;
- p->next = pNew;
- p = pNew->prior;
-
- return;
- }
-
- void delect_list(PNODE pHead, int pos, int *val)
- {
- int i;
- PNODE p = pHead;
-
- if(length_list(pHead) == 0)
- {
- printf("链表为空,没有内容可以删除!/n");
- exit(-1);
- }
- if((pos > length_list(pHead)) || (pos <= 0))
- {
- printf("删除元素的位置不是合法位置,删除失败!/n");
- exit(-1);
- }
- for(i = 0; i < pos-1; i++)
- {
- p = p->next;
- }
- if(NULL == p->next->next)
- {
- *val = p->next->data;
- p->next = NULL;
- }
- else if(NULL == p->next->next->next)
- {
- *val = p->next->data;
- p->next->next = NULL;
-
- }
- else
- {
- *val = p->next->data;
- p->next = p->next->next;
- p->next->next->prior = p;
- }
-
- return;
- }
-
- int find_list(PNODE pHead, int val,int *pos)
- {
- PNODE p = pHead;
- int i = 0;
-
- while(p != NULL)
- {
- i++;
- if(p->data == val)
- {
- *pos = i-1;
- return 0;
- }
- p = p->next;
- }
- return 1;
- }
(sunsea1026) |