一、雙向鏈表的結構及數(shù)據(jù)定義
#define ERROR0
#define TRUE1
#define FALSE0
#define OK1
#define MAXSIZE20/* 存儲空間初始分配量 */
//頭結點數(shù)據(jù)
#define HeadNodeData -1
typedef int Status;/* Status是函數(shù)的類型,其值是函數(shù)結果狀態(tài)代碼，如OK等 */
typedef int ElemType;/* ElemType類型根據(jù)實際情況而定，這里假設為int */
//定義結點
typedef struct Node{
? ? structNode*prior;
? ? ElemTypedata;
? ? structNode*next;
}Node;
typedef struct Node *LinkList;
二、創(chuàng)建雙向鏈表
Status CreateLinkList(LinkList *L){
? ? //創(chuàng)建一個頭結點
? ? *L = (LinkList)malloc(sizeof(Node));
? ? if(*L ==NULL) {
? ? ? ? returnERROR;
? ? }
? ? (*L)->data=HeadNodeData;//無效數(shù)據(jù)
? ? (*L)->next? =NULL;
? ? (*L)->prior=NULL;
? ? //新增數(shù)據(jù)
? ? LinkListp = *L;
? ? LinkListtemp;
? ? for(inti=0; i<10; i++) {
? ? ? ? //創(chuàng)建一個新結點
? ? ? ? temp = (LinkList)malloc(sizeof(Node));
? ? ? ? temp->data= i;
? ? ? ? temp->next=NULL;
? ? ? ? temp->prior=NULL;
? ? ? ? //為新增的結點建立雙向鏈表關系
? ? ? ? //temp 是p的后繼
? ? ? ? p->next= temp;
? ? ? ? //p 是temp的前驅(qū)
? ? ? ? temp->prior= p;
? ? ? ? //p指向最后一個結點
? ? ? ? p = temp;
? ? }
? ? returnOK;
}
三、打印循環(huán)鏈表的元素
void display(LinkList L){
? ? if(L ==NULL) {
? ? ? ? printf("打印的雙向鏈表為空!\n");
? ? ? ? return;
? ? }
? ? //指向第一個元素（非頭結點）
? ? LinkListtemp = L->next;
? ? while(temp) {
? ? ? ? printf("%d? ",temp->data);
? ? ? ? temp = temp->next;
? ? }
? ? printf("\n");
}
四、雙向鏈表插入元素
Status InsertList(LinkList *L,int index,ElemType data){
? ? //參數(shù)檢查
? ? if(index<1|| *L ==NULL) {
? ? ? ? returnERROR;
? ? }
? ? //新建結點
? ? LinkList temp = (LinkList)malloc(sizeof(Node));
? ? temp->data= data;
? ? temp->next=NULL;
? ? temp->prior=NULL;
? ? //指向頭結點
? ? LinkListp = *L;
? ? //找到插入位置的上一個結點
? ? inti=1;
? ? while(p && i
? ? ? ? p = p->next;
? ? ? ? i++;
? ? }
? ? //如果插入的位置超過鏈表本身的長度
? ? if(p ==NULL) {
? ? ? ? returnERROR;
? ? }
? ? //判斷插入位置是否為鏈表尾部;
? ? if(p->next==NULL) {
? ? ? ? p->next= temp;
? ? ? ? temp->prior= p;
? ? }else{
? ? ? ? //新結點的next指向p的next
? ? ? ? temp->next= p->next;
? ? ? ? //p的下一個結點的prior指向temp
? ? ? ? p->next->prior= temp;
? ? ? ? //新結點的prior指向p
? ? ? ? temp->prior= p;
? ? ? ? //p的next指向新結點
? ? ? ? p->next= temp;
? ? }
? ? returnOK;
}
五、刪除雙向鏈表指定位置上的結點
Status DeleteList(LinkList *L,int index,ElemType *data){
? ? //
? ? if(*L ==NULL|| index<1) {
? ? ? ? returnERROR;
? ? }
? ? //找到要刪除位置的上一個結點
? ? LinkListp = *L;
? ? for(inti=1; i
? ? ? ? p = p->next;
? ? }
? ? if(p==NULL) {
? ? ? ? returnERROR;
? ? }
? ? //指向要刪除的結點
? ? LinkListdelTemp = p->next;
? ? //p的next指向要刪除結點的下一個結點
? ? p->next= delTemp->next;
? ? //如果delTemp不是最后一個結點，則delTemp的下一個結點的prior指向p
? ? if(delTemp->next!=NULL) {
? ? ? ? delTemp->next->prior= p;
? ? }
? ? //將值帶回去
? ? *data = delTemp->data;
? ? //將要刪除結點回收
? ? free(delTemp);
? ? returnOK;
}
六、刪除指定元素
Status DeleteListVAL(LinkList *L,ElemType data){
? ? if(*L ==NULL|| data ==HeadNodeData) {
? ? ? ? returnERROR;
? ? }
? ? LinkListp = (*L)->next;
? ? while(p) {
? ? ? ? if(p->data== data) {
? ? ? ? ? ? //找到對應數(shù)據(jù),p是要被刪除的結點
? ? ? ? ? ? //p的前一個結點的next指向p的next
? ? ? ? ? ? p->prior->next= p->next;
? ? ? ? ? ? //不是最后一個結點,則p的下一個結點的prior指向p的前一個結點
? ? ? ? ? ? if(p->next!=NULL) {
? ? ? ? ? ? ? ? p->next->prior= p->prior;
? ? ? ? ? ? }
? ? ? ? ? ? //
? ? ? ? ? ? free(p);
//? ? ? ? ? ? break;//只刪除第一次出現(xiàn)的那個
? ? ? ? }
? ? ? ? //沒有找到該結點,則繼續(xù)移動指針p
? ? ? ? p = p->next;
? ? }
? ? returnOK;
}
七、在雙向鏈表中查找元素
int SelectList(LinkList L,ElemType elem){
? ? if(L ==NULL) {
? ? ? ? return HeadNodeData;
? ? }
? ? //指向首元結點
? ? LinkListp = L->next;
? ? inti =1;
? ? while(p) {
? ? ? ? if(p->data== elem) {
? ? ? ? ? ? returni;
? ? ? ? }
? ? ? ? p = p->next;
? ? ? ? i++;
? ? }
? ? return HeadNodeData;
}
八、在雙向鏈表中更新結點
StatusReplaceList(LinkListL,intindex,ElemTypenewData){
? ? if(L ==NULL|| index<1) {
? ? ? ? returnERROR;
? ? }
? ? LinkListp = L->next;
? ? inti=1;
? ? if(p && i
? ? ? ? p = p->next;
? ? ? ? i++;
? ? }
? ? if(p ==NULL) {
? ? ? ? returnERROR;
? ? }
? ? p->data= newData;
? ? returnOK;
}
九、調(diào)用
intmain(intargc,constchar* argv[]) {
? ? LinkList L;
? ? CreateLinkList(&L);
? ? display(L);
? ? intindex;
? ? ElemTypedata;
? ? printf("請輸入要插入的位置和值：\n");
? ? scanf("%d %d",&index,&data);
? ? InsertList(&L,index,data);
? ? display(L);
? ? printf("請輸入要刪除的位置1：\n");
? ? scanf("%d",&index);
? ? DeleteList(&L, index, &data);
? ? display(L);
? ? printf("請輸入要刪除的位置2：\n");
? ? scanf("%d",&index);
? ? DeleteList(&L, index, &data);
? ? display(L);
? ? printf("請輸入要刪除的位置3：\n");
? ? scanf("%d",&index);
? ? DeleteList(&L, index, &data);
? ? display(L);
? ? printf("請輸入要刪除的數(shù)據(jù)1：\n");
? ? scanf("%d",&data);
? ? DeleteListVAL(&L, data);
? ? display(L);
? ? printf("請輸入要刪除的數(shù)據(jù)2：\n");
? ? scanf("%d",&data);
? ? DeleteListVAL(&L, data);
? ? display(L);
? ? printf("請輸入要查詢的數(shù)據(jù)1：\n");
? ? scanf("%d",&data);
? ? index =SelectList(L, data);
? ? printf("數(shù)據(jù)在位置：%d \n",index);
? ? printf("請輸入要查詢的數(shù)據(jù)2：\n");
? ? scanf("%d",&data);
? ? index =SelectList(L, data);
? ? printf("數(shù)據(jù)在位置：%d \n",index);
? ? printf("請輸入要查詢的數(shù)據(jù)3：\n");
? ? scanf("%d",&data);
? ? index =SelectList(L, data);
? ? printf("數(shù)據(jù)在位置：%d \n",index);
? ? return0;
}
