首页   新闻   小组   威客   人才   下载   博客   代码贴   在线编程   论坛  
注册 | 登录

线性链表基本操作实现

作者在 2011-10-09 13:36:18 发布以下内容
//函数结果状态
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define NULL 0
#define OVERFLOW -2

#include<iostream>
#include<stdio.h>
#include<malloc.h>
using namespace std;

typedef int Status;//Staus是函数的类型，其值是函数结果
typedef int DateType; //DateType可以使相应任何的数据类型如int、float、char

//结点类型定义
typedef struct LNode
{
     DateType date;//结点的数据域
     struct LNode *next;//结点的指针域
}LNode;
typedef LNode *LinkList;

Status InitList_L(LinkList &L)//初始化单链表
{
L = (LinkList)malloc(sizeof(LNode));//L指向头节点，头节点数据域为空
L->next=NULL;
return 1;
}

Status DispList_L(LinkList &L)//输出单链表
{
LinkList p = L->next;
while(p != NULL)
{
printf("%d ",p->date);
p = p->next;
}
return OK;
}

Status CreateListTou(LinkList &L,int n)//头插法创建长度为n的单链表，带头结点
{
int i;
printf("请输入要创建的链表的长度:\n");
scanf("%d",&n);
LNode *p;
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL; //先建立一个带头结点的单链表
printf("请输入元素值:\n");
for(i = n;i > 0;i--)
{
p = (LinkList)malloc(sizeof(LNode));//生成新结点
scanf("%d",&p->date);//输入元素值
p->next = L->next;//使新结点指向链首
L->next = p;//插入到表头
}
return OK;
}

Status ListLength_L(LinkList L) //求单链表的长度
{
LinkList p=L;
int n=0;
while(p->next!=NULL)
{
n++;
p=p->next;
}
return(n);
}// ListLength_L

Status ListEmpty_L(LinkList L) //判断单链表是否为空，若为空返回TRUE，否则返回FALSE
{
if(L->next == NULL)
return TRUE;
else 
return FALSE;
}

Status DestroyList_L(LinkList &L) //销毁一个单链表
{
LinkList p = L,q = p->next;
while(q != NULL)
{
free(p);
p = q;
q = p->next;
}
free(p);
return OK;
}

Status GetElem_L(LinkList L, int i, DateType &e) //用e返回L中第i个数据元素的值
{
// L为带头结点的单链表的头指针。
// 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
int j=0;
LinkList p=L;//初始化，p指向第一个结点，j为计数器
while(j < i && p != NULL)//顺时针向后查找，直到p指向第i个元素或p为空
{
p = p->next;
++j;
}
if(!p || j > i)
return ERROR;//第i个元素不存在
e = p->date;//取第i个元素
return OK;
}

Status LocateElem_L(LinkList L,DateType e)//在链表中按元素值查找，返回该元素在链表中的位序
{
LinkList p = L->next;
int i = 1;
while(p != NULL && p->date != e)//判断待查找结点的值是否与待定值相等
{
p = p->next;
i++;
}
if(p)
printf("查找成功!是第%d个元素。\n",i);
return  OK;
}

Status ListInsert_L(LinkList &L,int i,DateType e)//在带头结点的单链表L中第i个位置之前插入元素e
{
LinkList p = L,s;
int j = 0;
/*
找到插入节点的上一个元素，如果是头节点则退出，当i=1时表示头节点，i=2时，表示第一个元素
*/
while(p != NULL && j < i - 1)//寻找第i-1个节点
{
j++;
p = p->next;//移向下一个结点
}
if(p == NULL)//i小于1或者大于表长加1,不能插入
{
getchar();
printf("Insert error!Any key to continue.\n");
getchar();
return ERROR;
}
else
{
s = (LinkList)malloc(sizeof(LNode));//生成新结点
s->date = e;//插入
s->next = p->next;
p->next = s;
getchar();
printf("Success!Any key to continue.\n");
DispList_L(L);
getchar();
return  OK;
}
}//时间复杂度为O(n)

Status ListDelete_L(LinkList &L,int i,DateType &e)//在带头结点的单链表L中,删除第i个元素并返回其值
{
LinkList p = L,s;
int j = 0;
while(p->next && j < i - 1)//寻找第i个节点,并指向其前驱
{
++j;
p = p->next;//移向下一个结点
}
if(!(p->next) || j > i - 1)//删除位置不合理
{
getchar();
printf("Delete error!Any key to continue.\n");
getchar();
return ERROR;
}
else
{
s = p->next;
p->next = s->next;//从链表中删除
e = s->date;
free(s);//释放s
return  OK;
}
}//时间复杂度为O(n)

Status InversionList_L(LinkList &L)//将一个链表逆置
{
LinkList p = L->next,q = L->next;
L->next=NULL;
while(p != NULL)
{
q = q->next;
p->next=L->next;
L->next=p;
p=q;
}
return OK;
}

/*void  ListInverse_L(LinkList &L)
{
//----单链表的就地逆置----//
LNode *p,*q;
    p=L->next;
L->next=NULL;
    while(p!=NULL)
{
        q=p->next;
p->next=L->next;
L->next=p;
p=q;
    }
 }*/

Status MaxAndMinList_L(LinkList L,DateType &e1,DateType &e2)//找最大值最小值并返回其值
{
LinkList p = L->next,q = L->next;
int max = p->date,min = p->date;
while(p != NULL)
{
if(p->date >= max)
max = p->date;
if(p->date <= min)
max = p->date;
p = p->next;
}
e1 = max;
e2 = min;
printf("最大值为:%d\n",e1);
printf("最小值为:%d\n",e2);
return OK;
}

Status ListMerge_L(LinkList &La,LinkList &Lb,LinkList &Lc)//将A 表和B表归并成一个按元素值递减有序排列的线性表C
{
return OK;
}

Status ListDelete1_L(LinkList &L,DateType mink,DateType maxk)//在线性单链表中删除值介于mink和maxk之间的结点,并输出删除后的链表
{
LinkList p = L,q;
if(mink >= maxk)
return ERROR;
while(p->next != NULL)
{
if(p->next->date > mink && p->next->date < maxk)
{
q = p->next;
p->next = q->next;//从链表中删除
free(q);//释放q
}
else
p = p->next;
}
cout << "After delete:" << endl;
DispList_L(L);
return OK;
}

void output()//边框
{
     int i;
     for(i = 0;i < 10;i ++)
        printf(" ");
     for(i = 0;i < 39;i ++)
        printf("*");
     printf("\n");
}

void mainpp()//显示窗口
{
     int i;
     output();
     for(i = 0;i < 10;i ++)
        printf(" ");
        printf("*   ");
     printf("1.建立一个单链表");
     for(i = 0;i < 18;i++)
        printf(" ");
        printf("*");
        printf("\n"); 
     for(i = 0;i < 10;i ++)
        printf(" ");
        printf("*   ");
     printf("2.输出一个单链表");
     for(i = 0;i < 18;i++)
        printf(" ");
        printf("*");
        printf("\n"); 
     for(i = 0;i < 10;i ++)
        printf(" ");
        printf("*   ");
     printf("3.在顺序表中查找元素位序");
     for(i = 0;i < 10;i ++)
        printf(" ");
        printf("*");
        printf("\n");
     for(i = 0;i < 10;i ++)
        printf(" ");
        printf("*   ");
printf("4.求单链表的长度");
     for(i = 0;i < 18;i++)
        printf(" ");
        printf("*");
        printf("\n"); 
     for(i = 0;i < 10;i ++)
        printf(" ");
        printf("*   ");
     printf("5.判断单链表中是否为空");
     for(i = 0;i < 12;i++)
        printf(" ");
        printf("*");
        printf("\n"); 
     for(i = 0;i < 10;i++)
        printf(" ");
        printf("*   ");
     printf("6.从销毁一个单链表");
     for(i = 0;i < 16;i++)
        printf(" ");
        printf("*");
        printf("\n"); 
     for(i = 0;i < 10;i++)
        printf(" ");
        printf("*   ");
printf("7.求第i个数据元素的值");
     for(i = 0;i < 13;i++)
        printf(" ");
        printf("*");
        printf("\n"); 
     for(i = 0;i < 10;i++)
        printf(" ");
        printf("*   ");
printf("8.求元素e在链表中的位序");
     for(i = 0;i < 11;i++)
        printf(" ");
        printf("*");
        printf("\n"); 
     for(i = 0;i < 10;i++)
        printf(" ");
        printf("*   ");
printf("9.在单链表L中第i个位置之前插入e");
     for(i = 0;i < 3;i++)
        printf(" ");
        printf("*");
        printf("\n"); 
     for(i = 0;i < 10;i++)
        printf(" ");
        printf("*   ");
printf("10.删除单链表L中第i个元素并返回");
     for(i = 0;i < 3;i++)
        printf(" ");
        printf("*");
        printf("\n"); 
     for(i = 0;i < 10;i++)
        printf(" ");
        printf("*   ");
printf("11.将链表逆置");
     for(i = 0;i < 21;i++)
        printf(" ");
        printf("*");
        printf("\n"); 
     for(i = 0;i < 10;i++)
        printf(" ");
        printf("*   ");
printf("12.找出链表中的最值");
     for(i = 0;i < 15;i++)
        printf(" ");
        printf("*");
        printf("\n"); 
     for(i = 0;i < 10;i++)
        printf(" ");
        printf("*   ");
printf("13.删除表中介于mink与maxk的元素");
     for(i = 0;i < 3;i++)
        printf(" ");
        printf("*");
        printf("\n"); 
     for(i = 0;i < 10;i++)
        printf(" ");
        printf("*   ");
     printf("0.退           出 "); 
     for(i = 0;i < 16;i++)
        printf(" ");
        printf("*");
        printf("\n"); 
     output(); 
}

int main()
{     
int n = 0,i,j,f,m,k = 1,d = 0,t = 0,h = 0,g = 0,a[] = {0},x,y,z,e1,e2,mink,maxk;
LinkList l;
InitList_L(l);//初始化单链表
mainpp();
    while(k) 
{
printf("请选择0--13：");
scanf("%d",&m);
getchar();
switch(m)
{
case 0:exit(0);
case 1:
{
CreateListTou(l,n);
printf("建立的单链表为:\n");
DispList_L(l);
printf("\n");
break;
}
case 2:
{
DispList_L(l);
printf("\n");
break;
}
case 3:
{
printf("Input date：");
scanf("%d",&x);
d = LocateElem_L(l,x);
printf("要查找的元素的定位：%d\n",k);
                printf("\n");
                break;
}
case 4:
{
t = ListLength_L(l);
printf("该链表的长度为:%d\n",t);
break;
}
case 5:
{
if(ListEmpty_L(l))
printf("该链表为空!\n");
else 
printf("该链表不为空!\n");
break;
}
case 6:
{
if(DestroyList_L(l))
printf("Destroy Success!\n");
else
printf("Destroy Fail!\n");
break;
}
case 7:
{
printf("请输入要取的元素的位序号:");
fflush(stdin);
scanf("%d",&i);
h = GetElem_L(l,i,x);
printf("该链表中第%d个元素为:%d\n",i,h);
break;
}
case 8:
{
printf("Input date::");
scanf("%d",&x);
g = LocateElem_L(l,x);
printf("要查找的元素%d的位序为:%d\n",x,g);
break;
}
case 9:
{
printf("Input position:");
scanf("%d",&j);
printf("Input date:");
scanf("%d",&y);
ListInsert_L(l,j,y);
printf("\n");
break;
}
case 10:
{
printf("请输入要删除的位置:");
scanf("%d",&f);
ListDelete_L(l,f,z);
printf("Success!Any key to continue.\n");
printf("The date is %d.\n",z);
printf("After Delete:\n");
DispList_L(l);
break;
}
case 11:
{
InversionList_L(l);
printf("After Inversion:\n");
DispList_L(l);
break;
}
case 12:
{
MaxAndMinList_L(l,e1,e2);
break;
}
case 13:
{
cout << "Input mink and maxk." <<endl;
cin >> mink >> maxk;
ListDelete1_L(l,mink,maxk);
printf("\n");
break;
}
default :exit(0);
}
printf("继续运行吗？Y（1）/N（0）：");
scanf("%d",&k);
if(k == 0)
exit(0); 
}
return 0;
}
数据结构 | 阅读 519 次
收藏
文章评论，共0条
游客请输入验证码
丁凯洋的博客

丁凯洋
浏览1626次
文章分类
文章归档
最新评论