❶ 雙向鏈表的順序插入演算法
#include <stdio.h>
#include <stdlib.h>
typedef struct tagDbNode
{
int num;
struct tagDbNode * pre;
struct tagDbNode * next;
} DbNode, * pdbNode;
//創建結點
pdbNode CreateNode(int num)
{
pdbNode pnode = (pdbNode)malloc(sizeof(DbNode));
pnode->num = num;
pnode->pre = pnode->next = pnode; //創建新結點時，讓其前驅和後繼指針都指向自身
return pnode;
}
//創建鏈表
pdbNode CreateList(int head) //參數給出表頭結點數據 （表頭結點不作為存放有意義數據的結點）
{
pdbNode pnode = (pdbNode)malloc(sizeof(DbNode));
pnode->num = head;
pnode->pre = pnode->next = pnode;
return pnode;
}
//獲取鏈表的長度
int GetLength(pdbNode *node) // 參數為鏈表的表頭結點
{
int i=1;
pdbNode x=*node;
pdbNode y=x->next;
while(y!=x)
{
y=y->next;
i++;
}
return(i);
}
//插入新結點,順序插入
pdbNode InsertNode(pdbNode *node,int num) // 參數1是鏈表的表頭結點，參數2是要插入的結點（結點數據為num）
{
pdbNode x=*node;
pdbNode y=x;
x=x->next;
if(y->num<num)
{
pdbNode a=(pdbNode)malloc(sizeof(tagDbNode));
a->num=num;
a->next=y;
a->pre=y->pre;
y->pre->next=a;
y->pre=a;
(*node)=a;//
return a;
}
while(x!=y)
{
if(x->num<num)
{
pdbNode a=(pdbNode)malloc(sizeof(tagDbNode));
a->num=num;
a->next=x;
a->pre=x->pre;
x->pre->next=a;
x->pre=a;
return y;
}
else
{
x=x->next;
}
}
pdbNode a=(pdbNode)malloc(sizeof(tagDbNode));
a->num=num;
a->next=y;
a->pre=y->pre;
y->pre->next=a;
y->pre=a;
return y;
}
//列印整個鏈表
void PrintList(pdbNode node) // 參數為鏈表的表頭結點
{
pdbNode pnode;
if (NULL == node) return;
pnode= node->next;
printf("%d ", node->num);
while (pnode != node)
{
printf("%d ", pnode->num);
pnode = pnode ->next;
}
printf("\n");
}
//測試程序
#include <stdio.h>
#include <stdlib.h>
//#include "dblist.h"
#define FALSE 0
#define TRUE 1
void main()
{
int nChoose;
int num;
bool bFlag = FALSE;
pdbNode pnode;
pdbNode list = CreateList(0);
pdbNode *head=&list;//是指向指針的指針，因為頭結點會變，而這種變化要傳回來，只能用指向指針的指針
while(FALSE == bFlag)
{
printf("主目錄\n");
printf("1. 插入一個節點\n");
printf("2. 刪除一個節點\n");
printf("3. 查找節點\n");
printf("4. 列印鏈表\n");
printf("5. 刪除鏈表\n");
printf("0. 退出\n\n");
scanf("%d", &nChoose);
switch(nChoose)
{
case 1:
printf("請輸入要插入的數據:");
scanf("%d", &num);
list = InsertNode(head, num);
PrintList(*head);
break;
case 2:
printf("請輸入要刪除的數據:");
scanf("%d", &num);
//DeleteNode(*head, num);
break;
case 3:
printf("請輸入要查找的數據:");
scanf("%d", &num);
//pnode = FindNode(list, num);
if (NULL != pnode)
{printf("查找成功!\n");
}
else
{ printf("沒有這個數據!\n");
}
break;
case 4:
PrintList(list);
break;
case 5:
//DeleteList(list);
break;
case 6:
printf("這各表的長度為： %d", GetLength(head));
break;
case 0:
//DeleteList(list);
bFlag = TRUE;
}
}
}
我的這個答案，在函數調用的時候，利用的是指向指針的指針，因為開始沒有注意到你用的函數有頭結點的返回值，所以和你原來給的變動較大，不過還是希望我寫的你可以理解，因為我的注釋較少（太懶了），所以，將就著看吧
❷ c語言數據結構（雙向鏈表排序）
#include<stdio.h>
#include<malloc.h>
#define ElemType int
int count=0;
typedef struct DulNode
{
ElemType data;
DulNode *prior;
DulNode *next;
}DulNode,*DulLinkList;
//初始化鏈表，結束後產生一個頭結點指針
void InitDLList(DulLinkList *L)
{
(*L)=(DulLinkList)malloc(sizeof(DulNode));
(*L)->next=*L;
(*L)->prior=(*L)->next;
}
//對鏈表進行插入操作
void ListInsert(DulLinkList *L)
{
int i=0,n;
ElemType temp;
DulNode *s,*p;
p=(*L)->next;
printf("請輸入插入元素數量：\n");
scanf("%d",&n);
count=n;
printf("請輸入%d個自然數\n",n);
while(i<n)
{
scanf("%d",&temp);
s=(DulNode*)malloc(sizeof(DulNode));
s->data=temp;
while((p!=(*L))&&(p->data<temp))//查找所要插入的位置
{
p=p->next;
}
s->prior=p->prior;//新節點的插入
s->next=p;
p->prior->next=s;
p->prior=s;
p=(*L)->next;//將指針回指到鏈表第一個非空節點，主要是為了下次查找插入位置
i++;
}
}
void Display(DulLinkList L)
{
DulNode *p;
p=L->next;
printf("雙向鏈表中的數據為:\n");
while(p!=L)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
void Sort(DulLinkList *L)
{
ElemType temp;
DulNode *p,*q;
p=(*L)->next;
q=(*L)->prior;
if(count%2!=0)
q=q->prior;
p=p->next;
while(p!=q)
{
temp=p->data;
p->data=q->data;
q->data=temp;
p=p->next;
if(p!=q) //第二題只需交換節點數據
q=q->prior;//這幾個if else語句需要仔細
else
break;
if(p!=q)
p=p->next;
else
break;
if(p!=q)
q=q->prior;
else
break;
}
}
void main()
{
DulLinkList L;
InitDLList(&L);//初始化鏈表
ListInsert(&L);//順序插入數據
Display(L);//顯示結果
Sort(&L);//第二題操作
Display(L);//第二題輸出結果
}