資料結構雙向循環連結清單的增删

建立一個雙向連結清單并實作增加和删除以及求表長

代碼如下：

#include<string.h>
#include<stdlib.h>
#include<errno.h>

#define OK 1
#define ERROR 0

typedef struct {
	char name[8];
	int id;
	int score;
} student;

typedef struct LNode {
	student date ;
	struct LNode *pre;
	struct LNode *next;
} LNode, *LinkList;

           

主函數部分

int main(){

    LinkList L;
	L = ( LinkList ) malloc ( sizeof ( LinkList ) );
	L -> next = NULL;
	//建立連結清單
    CreateLinkList(L);
    PrintList(L);
    //求表長不包括頭節點
    ListLen(L);
    //删除元素
    ListDelete(L);
    PrintList(L);
    //插入元素
    ListInsert(L);
    PrintList(L);
}
           

函數方法

int CreateLinkList( LinkList L )
{
    char n[8];
    int t, s;
    LinkList p, newn;
    p = L;   /*尾指針指向頭節點*/
    FILE *r;
    if ( ( r = fopen ("as.txt", "r" ) ) == NULL ) {
		printf("can't open the file!!!\n");
		printf("error:%s\n", strerror(errno));
		exit(0);
    }
    while ( fscanf ( r, "%s%d%d", n, &t, &s ) != EOF ) {
		newn = ( LNode * ) malloc ( sizeof ( LNode ) );
		strcpy ( newn -> date.name, n );/*字元串初始化後不能直接指派需要調用strcpy()*/
		newn -> date.id = t;
		newn -> date.score = s;
		newn->next=NULL;     /*新節點後指指針域置空*/
		newn->pre=p;         //新節點指向上一節點
		p->next=newn;       /*前一個節點指針（即原先的尾指針指向的節點）指向新節點*/
		p=newn;
    }
    fclose(r);
    L->pre=p;          //頭尾相連
    p->next=L;
}

           

/*
 *擷取該連結清單的長度（不包括頭結點）
*/
int ListLen(LinkList L){
	LinkList p;
	p=L;
	int len = 0;
	while(p->next!=L ){
		p = p->next;
		len++;
	}
	printf("表長為%d\n\n",len);
	return len;
}

           

void PrintList (LinkList L) {
    LinkList p;
    p=L;
    printf("姓名\t\t\t\t學号\t\t\t\t成績\n");
    while ( p->next!=L )/*當循環條件是p時，因為頭節點資料域為空每次會輸出一行亂碼*/
    {
    	printf("%s\t\t\t\t%d\t\t\t\t%d\n",p->next->date.name,p->next->date.id,p->next->date.score);
    	p = p -> next;
    }
    printf("\n");
}

           

int ListInsert(LinkList L )
{
    LinkList p,newn;
    int k,j=0;
    student s;
    p=L;
    printf("輸入要插入的節點坐标\n");
    scanf("%d",&k);
    while(p!=NULL&&j<k)
    {
        p=p->next;
        j++;
    }
    if((j!=k)||(p==NULL))
    {
      printf("要插入的節點不存在");
      return ERROR;
    }
    printf("================輸入要插入的學生資訊==============\n");
    printf("*****姓名:");	scanf("%s",s.name);
	printf("*****學号:");	scanf("%d",&s.id);
	printf("*****成績:");	scanf("%d",&s.score);
	printf("輸入完成\n\n");
    newn=(LNode*)malloc(sizeof(LNode));
    newn->date= s ;
    newn->pre=p->pre;         //将原先位置的節點的前指指針指向的的位址給新插入的節點的前指指針
    p->pre->next=newn;        //将新節點的位址給原先節點的前一個節點，新節點與前節點對接完成
    newn->next=p;             //新節點的後指指針指向原先節點
    p->pre=newn;               //原先節點的前指指針指向新插入節點，新節點與後節點對接完成
    return OK;
}

           

int ListDelete ( LinkList L ) {

    int i, j = 0;
    LinkList p;
    LinkList q= L;
    p = L->next;
    printf("輸入要删除的節點位置\n");
    scanf("%d", &i);
    while (p->next!=L&&j<i-1)
    {
        p = p->next;
        j++;
    }
     if ((j!=i-1)||(i > ListLen(q))){
        printf("要删除的節點不存在\n");
        return ERROR;
    }
    p->pre->next=p->next; //将要删除節點下一個節點位址給要删除節點前一節點的後指指針
    p->next->pre=p->pre; //将要删除節點的前一個節點的位址給要删除節點的下一節點
    free(p);
    return OK;
}