加载中…
个人资料
谢先斌
谢先斌
  • 博客等级:
  • 博客积分:0
  • 博客访问:392,805
  • 关注人气:201
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

双向链表的基本操作

(2012-06-21 09:40:11)
标签:

链表

元素

指定

遍历

删除

分类: ACM/C语言解答

实验三:双向链表的基本操作

    1.利用尾插法建立一个双向链表。

    2.遍历双向链表。

    3.实现双向链表中删除一个指定元素。

4.在非递减有序双向链表中实现插入元素e仍有序算法。

    5.判断双向链表中元素是否对称若对称返回1否则返回0。

6.设元素为正整型,实现算法把所有奇数排列在偶数之前。

    7.在主函数中设计一个简单的菜单调试上述算法。

 

#include <stdio.h>

#include <stdlib.h>

 

#define ERROR -1

#define OK 1

#define OVERFLOW -2

 

typedef int ElemType;

typedef int Status;

 

 

typedef struct DuLNode{

         ElemType data;

         struct DuLNode *prior;

         struct DuLNode *next;

}DuLNode, * DuLinkList;

 

//创建双链表

Status InsertDuLinkList_real(DuLinkList L)

{

         int n,i,c;

         printf("请输入要创建双链表的长度n=");

         scanf("%d",&n);

        

         DuLinkList p,dl;

        

         dl = L;

         printf("请依次输入数据:");

         for(i=0; i<n; i++)

         {

                   if(!(p=(DuLinkList)malloc(sizeof(DuLNode))))

                            return OVERFLOW;

                   scanf("%d",&c);

                   p->data = c;

                   dl->next = p;

                   p->prior = dl;

                   p->next = L;

                   L->prior = p;

                   dl = p;

         }

         return OK;

}

 

//遍历双链表

Status pDuLinkList(DuLinkList L)

{

         DuLinkList dl;

         dl = L->next ;

         while(dl->next != L)

         {

                   printf("%d ",dl->data);

                   dl = dl->next;

         }

         printf("%d\n",dl->data);

         return OK;

}

 

DuLinkList GetElemP_DuL(DuLinkList L, ElemType i)

{

         DuLinkList dl;

         dl = L->next;

         while(dl != L)

         {

                   if(dl->data == i)

                            return dl;

         }

         return NULL;

}

 

//双链表的删除,实现双向链表中删除一个指定元素

Status LinkDelete_Dul(DuLinkList L, int i)

{

         DuLinkList p;

         if(!(p = GetElemP_DuL(L, i)))

                   return ERROR;

        

         p->prior->next = p->next;

         p->next->prior = p->prior;

         free(p);

         return OK;

}

 

Status GetLengthOfDL(DuLinkList L)

{

         int n = 0;

         DuLinkList dl;

         dl = L->next;

         while(dl != L)

         {

                   n++;

                   dl = dl->next;

         }

         return n;

}

 

//实现双链表的指定位置的删除

Status LinkDelete_Dd(DuLinkList L, int i)

{

         if(i>GetLengthOfDL(L) || i<1)

         {

                   printf("删除下标非法!\n");

                   return ERROR;

         }

        

         DuLinkList dl;

         int n = 1;

         dl = L->next ;

         while(n < i)

         {

                   n++;

                   dl = dl->next;

         }

         //p = dl->prior;

         dl->prior->next = dl->next;

         dl->next->prior = dl->prior;

         free(dl);

         return OK;

}

 

//排序

Status sortDuLinkList(DuLinkList L)

{

         int n = GetLengthOfDL(L);

         //printf("%d",n);

         int t;

         DuLinkList p;

         for(int i=1; i<n; i++)

         {

                  p = L->next;

                   for(int j=0; j<n-i; j++)

                   {

                            if(p->data > p->next->data)

                            {

                                     t = p->data;

                                     p->data = p->next->data;

                                     p->next->data = t;

                            }

                            p = p->next;

                   }

         }

 

         return OK;

 

}

 

//插入

Status InsertDuL(DuLinkList L, int n)

       //printf("dd");

         DuLinkList p,dl;

         if(!(dl = (DuLinkList)malloc(sizeof(DuLNode))))

                   return OVERFLOW;

         p = L->next;

         dl->data = n;

         while(p->data < n)

                   p = p->next;

         printf("%d",p->data);

 

         p->prior->next = dl;

         dl->prior = p->prior;

         p->prior = dl;

         dl->next = p;

         return OK;

}

 

//判断双链表是否对称

Status isReturnDuL(DuLinkList L)

{

         DuLinkList p,q;

         p = L->next;

         q = L->prior;

         int n = GetLengthOfDL(L);

         if(n%2){

                   while(p->data==q->data&&p!=q){

                            p=p->next;q=q->prior;

                   }

                   if(q==p)

                            return 1;

                   else

                            return 0;

         }else{

                   while(p->data==q->data&&p->next!=q){

                            p=p->next;q=q->prior;

                   }

                   if(p->data==q->data)

                            return 1;

                   else

                            return 0;

         }

}

 

//实现算法把所有奇数排列在偶数之前

Status inLawSort(DuLinkList L)

{

         DuLinkList p,dl,p1;

         int i,n = GetLengthOfDL(L);

         i = 0;

         p = L->next;

         dl = L->prior;

         while(i < n)

         {

                   if((p->data)%2 != 0)

                   {

                            i++;

                            p = p->next;

                   }

                   else

                   {

                            p1 = p->next;

                            p->next->prior = p->prior;

                            p->prior->next = p->next;

 

                            p->next = L;

                            p->prior = dl;

                            dl->next = p;

                            L->prior = p;

                            dl = p;

                            p = p1;

                            i++;

                   }

         }

         return OK;

}

 

void print()

{

         printf("欢迎测试双链表,菜单如下:\n");

         printf("1.运用尾差法创建双链表\n");

         printf("2.遍历双向链表\n");

         printf("3.实现双链表删除一个指定元素\n");

         printf("4.在非递减有序双向链表中实现插入元素e仍有序\n");

         printf("5.判断双向链表中元素是否对称若对称返回1否则返回0\n");

         printf("6.实现算法把所有奇数排列在偶数之前\n");

         printf("0.EXIT\n");

         printf("请选择操作序号:");

}

 

 

 

int main()

{

         DuLinkList L;

         Status e,ch,n;

         bool flag = true;

        

         L = (DuLinkList)malloc(sizeof(DuLNode));

         L->prior = NULL;

         L->next = NULL;

         print();

         while(scanf("%d",&ch)!=EOF)

         {

                   switch(ch)

                   {

                   case 0:

                            flag = false;

                            break;

                   case 1:

                            if(InsertDuLinkList_real(L))

                                     printf("创建成功!\n");

                            else

                                     printf("创建失败!\n");

                            break;

                   case 2:

                            if(pDuLinkList(L))

                                     printf("遍历成功!\n");

                            else

                                     printf("遍历失败!\n");

                            break;

                   case 3:

                            printf("请选择删除方式:1.删除指定元素  2.删除制定下标\n");

                            printf("请输入选择序号e=");

                            scanf("%d",&e);

                            switch(e)

                            {

                            case 1:

                                     printf("请输入指定元素n=");

                                               scanf("%d",&n);

                                     if(LinkDelete_Dul(L,n))

                                               printf("指定元素已删除!\n");

                                     else

                                               printf("指定元素删除失败!\n");

                                     break;

                            case 2:

                                     printf("请输入指定下标n=");

                                     scanf("%d",&n);

                                     if(LinkDelete_Dd(L,n))

                                               printf("指定下标删除成功!\n");

                                     else

                                               printf("指定下标删除失败!\n");

                            }

                            break;

                   case 4:

                            printf("按非递减排序双链表!\n");

                            sortDuLinkList(L);

                            pDuLinkList(L);

                            printf("请输入插入的元素n=");

                            scanf("%d",&n);

                            if(InsertDuL(L, n))

                                     printf("插入成功!\n");

                            else

                                     printf("插入失败!\n");                               

                            break;

                   case 5:

                            if(isReturnDuL(L))

                                     printf("1\n");

                            else

                                     printf("0\n");

                            break;

                   case 6:

                            if(inLawSort(L))

                            {

                                     printf("奇前偶后排序成功!\n");

                                     pDuLinkList(L);

                            }

                            else

                                     printf("奇前偶后排序失败!\n");

                            break;

                   default:

                            printf("输入错误!\n");

                   }

                   if(!flag)

                            break;

         }

        

        

         return 0;

}

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有