本文共 4319 字,大约阅读时间需要 14 分钟。
data.h
#ifndef _DATA_H_#define _DATA_H_typedef struct DbNode{ int data; struct DbNode *left; struct DbNode *right;}DbNode;#endif
doubleLinklist.h
#ifndef DOUBLE_LINKLIST_H#define DOUBLE_LINKLIST_H#include "data.h"#includemain.c#include DbNode* CreateNode(int data){ DbNode *pnode = (DbNode*)malloc(sizeof(DbNode)); pnode->data = data; pnode->left = pnode->right = NULL;#ifdef DEBUG printf("%s data = %d\n",__FUNCTION__,data);#endif return pnode;}DbNode* CreateList(int head){ DbNode *pnode = (DbNode*)malloc(sizeof(DbNode)); pnode->data = head; pnode->left = pnode->right = NULL;#ifdef DEBUG printf("%s head = %d\n",__FUNCTION__,head);#endif return pnode;}DbNode* AppendNode(DbNode* head,int data){ DbNode* node = CreateNode(data); DbNode* p = head; DbNode* q; while(p != NULL) { q = p; p = p->right; } q->right = node; node->left = q;#ifdef DEBUG printf("%s data = %d\n",__FUNCTION__,data);#endif return head;}int GetLength(DbNode* head){ int count = 1; DbNode* pnode = NULL; if(head == NULL) return 0; pnode = head->right; while(pnode != NULL) { pnode = pnode->right; count++; } return count;}void PrintList(DbNode* head){ DbNode* pnode = NULL; if(head == NULL) return; pnode = head; printf("Double list show as below\n"); while(pnode != NULL) { printf("%d ",pnode->data); pnode = pnode->right; } printf("\n");}int FindNode(DbNode* head,int find_this_data){ int pos = 0; DbNode* pnode = head; if(head == NULL) return -1; while(pnode->right != NULL && pnode->data != find_this_data) { pnode = pnode->right; pos++; } /* * There is no this specific number * */ if(pnode->right == NULL && pnode->data != find_this_data) return -2; return pos + 1;}DbNode* FindNode2(DbNode* head,int data){ DbNode* pnode = head; /* * 链表为空 * */ if(head == NULL) return NULL; /* * 找到数据或者到达链表尾部就退出while循环 * */ while(pnode->right != NULL && pnode->data != data) pnode = pnode->right; /* * 没有找到数据为data的结点 * */ if(pnode->right == NULL && pnode->data != data) return NULL; return pnode;}void InsertNode(DbNode* head,int insert_after_this_pos,int insert_this_data){ /* * 如果头结点为空,什么都不操作 * */ DbNode* newNode = CreateNode(insert_this_data); int len; if(head == NULL) return; else len = GetLength(head); if(len < insert_after_this_pos) { printf("Insert out of range\n"); return; } DbNode* pnode = head; int tmpPos = 0; while(pnode->right != NULL && tmpPos < insert_after_this_pos - 1) { pnode = pnode->right; tmpPos++; } /* * 如果pnode是最后一个结点 * */ if(pnode->right == NULL) { pnode->right = newNode; newNode->left = pnode; } else//是中间的结点 { /* * 新结点的right指向pnode结点的下一个结点 * */ newNode->right = pnode->right; /* * pnode的下一个结点的left指向newNode * */ pnode->right->left = newNode; /* * pnode的right指向newNode * */ pnode->right = newNode; /* * newNode的left指向pnode * */ newNode->left = pnode; }}DbNode* DeleteNode(DbNode* head,int del_this_data){ DbNode* ptmp = NULL; DbNode* pnode = FindNode2(head,del_this_data); /* * 要删除的结点不存在,返回head不做任何操作 * */ if(pnode == NULL) { printf("There is no %d in the linklist\n",del_this_data); return head; } /* *要删除的结点是第一个结点 * */ else if(pnode->left == NULL) { /* * 让第二个结点作为头结点 * */ head = pnode->right; /* * 链表不为空 * */ if(head != NULL) head->left = NULL; } /* *要删除的结点是最后一个结点 *让倒数第二个结点的right指向null * */ else if(pnode->right == NULL) pnode->left->right = NULL; /* * 要删除的结点是中间的结点 * */ else { /* * pnode结点的上一个结点的right指向pnode的下一个结点 * */ pnode->left->right = pnode->right; /* * pnode的下一个结点的left指向pnode的上一个结点 * */ pnode->right->left = pnode->left; } free(pnode); return head;}#endif
#include "doubleLinklist.h"int main(){ DbNode* head = CreateList(0); int i; for(i = 1; i < 9; i++) head = AppendNode(head,i); PrintList(head); int len = GetLength(head); printf("len(linklist) = %d\n",len); printf("Find:"); int find; scanf("%d",&find); int res = FindNode(head,find); if(res < 0) printf("No this data\n"); else printf("Data pos = %d\n",res); printf("InsertPos[0,len] & data:"); int insertPos,insertData; scanf("%d,%d",&insertPos,&insertData); InsertNode(head,insertPos,insertData); printf("Insert %d after pos %d\n",insertData,insertPos - 1); PrintList(head); int del; printf("Delete data:"); scanf("%d",&del); head = DeleteNode(head,del); printf("Delete %d from linklist!!!\n",del); PrintList(head); return 0;}
转载地址:http://mxuhj.baihongyu.com/