代碼中為非循環的雙向鏈表，包括結點的插入、刪除等操作 [cpp] // LinkList_D.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include "stdio.h" #include "stdlib.h" #include "iostream" using namespace std; typedef int DataType; typedef struct DLNode { DataType data; struct DLNode * prior; struct DLNode * next; }DLNode,*DLinkList; void CreateDList(DLinkList &L,int n); void PrintDLinkList(DLinkList &L); int DListInset(DLinkList &L,int i,DataType e); int DListDelete(DLinkList &L,int i,DataType &e); int _tmain(int argc, _TCHAR* argv[]) { // 創建鏈表 DLinkList L; CreateDList(L,5); //創建具有5個結點的雙向鏈表 PrintDLinkList(L); // 輸出鏈表 // 測試插入元素 DListInset(L,1,100); //在第一個元素前插入元素 PrintDLinkList(L); DListInset(L,2,200); PrintDLinkList(L); // 測試刪除一個元素 printf("node deleted\n"); int e; DListDelete(L,2,e); PrintDLinkList(L); // 測試刪除一個元素 printf("node deleted\n"); DListDelete(L,6,e); PrintDLinkList(L); getchar(); getchar(); return 0; } // 創建長度為n的鏈表,在頭結點之前插入新的結點,非循環鏈表 void CreateDList(DLinkList &L,int n) { L=(DLinkList)malloc(sizeof(DLNode)); L->next=NULL; L->prior=NULL; printf("please input n nodes:\n"); DLinkList p=(DLinkList)malloc(sizeof(DLNode)); // 插入第一個結點 scanf("%d",&p->data); L->next=p; p->prior=L; p->next=NULL; // 插入其他的剩余結點 for(int i=n-1;i>0;--i) { DLinkList p=(DLinkList)malloc(sizeof(DLNode)); scanf("%d",&p->data); p->prior=L; L->next->prior=p; p->next=L->next; L->next=p; } } // 輸出結點 void PrintDLinkList(DLinkList &L) { DLinkList p=L->next; //指向第一個結點 while (p!=NULL) { printf("%5d",p->data); p=p->next; } printf("\n"); } // 在第i個元素之前插入元素 int DListInset(DLinkList &L,int i,DataType e) { DLinkList p=L->next; //指向第一個元素 int j=1; while(p&&j<i) { p=p->next; j++; } if (!p||j>i) { return -1; } DLinkList s=(DLinkList)malloc(sizeof(DLNode)); if(!s) return -1; s->data=e; s->prior=p->prior; p->prior->next=s; s->next=p; p->prior=s; return 1; } // 刪除指定位置的元素 int DListDelete(DLinkList &L,int i,DataType &e) { DLinkList p=L->next; // 指向第一個元素 int j=1; while(p&&j<i) { p=p->next; j++; } // 指向第i個元素 if(!p||j>i) return -1; if (p->next==NULL) // 刪除的元素為最後一個元素 { p->prior->next=p->next; } else { // 刪除的元素不是最後一個元素 p->prior->next=p->next; p->next->prior=p->prior; } } // LinkList_D.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include "stdio.h" #include "stdlib.h" #include "iostream" using namespace std; typedef int DataType; typedef struct DLNode { DataType data; struct DLNode * prior; struct DLNode * next; }DLNode,*DLinkList; void CreateDList(DLinkList &L,int n); void PrintDLinkList(DLinkList &L); int DListInset(DLinkList &L,int i,DataType e); int DListDelete(DLinkList &L,int i,DataType &e); int _tmain(int argc, _TCHAR* argv[]) { // 創建鏈表 DLinkList L; CreateDList(L,5); //創建具有5個結點的雙向鏈表 PrintDLinkList(L); // 輸出鏈表 // 測試插入元素 DListInset(L,1,100); //在第一個元素前插入元素 PrintDLinkList(L); DListInset(L,2,200); PrintDLinkList(L); // 測試刪除一個元素 printf("node deleted\n"); int e; DListDelete(L,2,e); PrintDLinkList(L); // 測試刪除一個元素 printf("node deleted\n"); DListDelete(L,6,e); PrintDLinkList(L); getchar(); getchar(); return 0; } // 創建長度為n的鏈表,在頭結點之前插入新的結點,非循環鏈表 void CreateDList(DLinkList &L,int n) { L=(DLinkList)malloc(sizeof(DLNode)); L->next=NULL; L->prior=NULL; printf("please input n nodes:\n"); DLinkList p=(DLinkList)malloc(sizeof(DLNode)); // 插入第一個結點 scanf("%d",&p->data); L->next=p; p->prior=L; p->next=NULL; // 插入其他的剩余結點 for(int i=n-1;i>0;--i) { DLinkList p=(DLinkList)malloc(sizeof(DLNode)); scanf("%d",&p->data); p->prior=L; L->next->prior=p; p->next=L->next; L->next=p; } } // 輸出結點 void PrintDLinkList(DLinkList &L) { DLinkList p=L->next; //指向第一個結點 while (p!=NULL) { printf("%5d",p->data); p=p->next; } printf("\n"); } // 在第i個元素之前插入元素 int DListInset(DLinkList &L,int i,DataType e) { DLinkList p=L->next; //指向第一個元素 int j=1; while(p&&j<i) { p=p->next; j++; } if (!p||j>i) { return -1; } DLinkList s=(DLinkList)malloc(sizeof(DLNode)); if(!s) return -1; s->data=e; s->prior=p->prior; p->prior->next=s; s->next=p; p->prior=s; return 1; } // 刪除指定位置的元素 int DListDelete(DLinkList &L,int i,DataType &e) { DLinkList p=L->next; // 指向第一個元素 int j=1; while(p&&j<i) { p=p->next; j++; } // 指向第i個元素 if(!p||j>i) return -1; if (p->next==NULL) // 刪除的元素為最後一個元素 { p->prior->next=p->next; } else { // 刪除的元素不是最後一個元素 p->prior->next=p->next; p->next->prior=p->prior; } }
