线性表11的作业题

fzquchs · 发表于 2016-2-16 01:17:36

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

最近一直在看小甲鱼老师的数据结构，以前没有学过数据结构这一门。由于是新鱼油，下载不了课件来学，只能看着视频，跟着老师一起
敲代码。看到单链表留下了作业，觉得蛮有意思。就根据前面学到的知识都用上了，比小甲鱼老师的多增加了一些功能，方便各位新手学习，对于高手的话就直接飘过吧~~~~~

#include <stdio.h>
#include <windows.h>
#include "time.h"
#define OK 1
#define ERROR 0
// #define TRUE 1
// #define FALSE 0
typedef int Status;
typedef int ElemType;
//链表结点结构
struct tagNode
{
ElemType data;
struct tagNode *next;
};
typedef struct tagNode *LinkList,Node;
///////////////////函数声明///////////////////////
//初始化空链表
Status InitList(LinkList* linkHead);
//求链表长度
int ListLength(LinkList L);
//获取中间结点元素
Status GetMidNode(LinkList L,ElemType *e);
//尾插法建立单链表
void CreateListTail(LinkList *L, int n);
//单链表整表删除
Status ClearList(LinkList *L);
//查看链表
Status PrintList(LinkList L);
//初始条件：顺序线性表L已存在， 1<=i<=ListLength(L)
//操作结果：在L中第i个位置之前插入新的数据元素e, L长度+1
Status ListInsert(LinkList *L, int i, ElemType e);
//链式存储结构删除链表某位的元素数据
Status ListDelete(LinkList *L, int i, ElemType* e);
//删除空链表
Status OverList(LinkList *L);
//////////////////////////////////////////////////
//初始化空链表
Status InitList(LinkList* linkHead)
{
LinkList r; //临时变量指针，用来存放结点地址，方便调用
*linkHead = (LinkList)malloc(sizeof(Node));
r = *linkHead; //结点的地址
if(r == NULL)
return ERROR;
r->data = 0;
r->next = NULL;
return OK;
}
//求链表长度
int ListLength(LinkList L)
{
int icount = 0;
if(L)
{
LinkList r = L->next;
while(r)
{
r = r->next;
icount++;
}
}
return icount;
}
//获取中间结点元素
Status GetMidNode(LinkList L,ElemType *e)
{
LinkList search, mid;
mid = search = L;
if(NULL == L)
return (*e=ERROR);
if(NULL == L->next)
return (*e=ERROR);
while( search->next != NULL )
{
//search移动的速度是 mid 的2倍
if( search->next->next != NULL )
{
search = search->next->next;
mid = mid->next;
}else
{
search = search->next;
}
}
*e = mid->data;
return OK;
}
//尾插法建立单链表
void CreateListTail(LinkList *L, int n)
{
LinkList p, r;
int i;
srand(time(0));
*L = (LinkList)malloc(sizeof(Node)); //我们传入地址
r = *L; //r是当前的结点
for(i = 0; i < n; i++)
{
p = (Node*)malloc(sizeof(Node));
p->data = rand()%100 +1;
r->next = p;
r = p;
printf("%d ",p->data);
}
printf("\n");
r->next = NULL;
}
//单链表整表删除
/*
单链表整表删除的算法思路如下：
声明结点p和q；
将第一个结点赋值给p，下一结点赋值给q；
循环执行释放p和将q赋值给p的操作；
*/
Status ClearList(LinkList *L)
{
LinkList p, q;
p = (*L)->next;
while(p)
{
q = p->next;
free(p);
p = q;
}
(*L)->next = NULL; //这样就剩下了一个头结点的空表
return OK;
}
//查看链表
Status PrintList(LinkList L)
{
if(L)
{
LinkList r = L->next;
while(r)
{
printf("%d ",r->data);
r = r->next;
}
}else
return ERROR;
printf("\n");
return OK;
}
//链式存储结构的线性表如：链表
//初始条件：顺序线性表L已存在， 1<=i<=ListLength(L)
//操作结果：在L中第i个位置之前插入新的数据元素e, L长度+1
Status ListInsert(LinkList *L, int i, ElemType e)
{
int j;
LinkList p, s;
p = *L;
j = 1;
//寻找i位置
while( p && j<i)
{
p = p->next;
j++;
}
//检测p是否到达链表尾NULL 或者没找到i
if( !p || j>i)
{
return ERROR;
}
//创建新结点
s = (LinkList)malloc(sizeof(Node));
//给新结点数据域赋值
s->data = e;
//修正新结点指针域
s->next = p->next;
p->next = s;
return OK;
}
//链式存储结构删除链表某位的元素数据
Status ListDelete(LinkList *L, int i, ElemType* e)
{
int j;
LinkList p, q;
p = *L;
j = 1;
//寻找第i位置的结点
//结果有3种可能：
//1：找到了，不过p是第i-1的结点，p->next就是要删除的结点
//2：到达NULL尾
//3：不存在i位置元素
while( p->next && j<i )
{
p = p->next;
++j;
}
//排除2、3可能
if( !(p->next) || j>i )
{
return ERROR;
}
//获取要删除结点到q
q = p->next;
//断链
p->next = q->next;
//保存删除结点数据
*e = q->data;
//回收创建结点时申请的内存
free(q);
return OK;
}
//删除空链表
Status OverList(LinkList *L)
{
LinkList r = NULL; //临时指针变量
r = *L;
if(r)
{
if( NULL == r->next )
{
//这个就是链表头结点，我们回收它
free(r);
*L = r = NULL;
return OK;
}
}
return ERROR;
}
//输出界面
void OutMenu()
{
printf("1.查看链表\n");
printf("2.创建链表(尾插法)\n");
printf("3.链表长度\n");
printf("4.中间结点值\n");
printf("5.整表删除,空表\n");
printf("6.删除空表，结束掉创建的线性表\n");
printf("7.在第3号位置插入23\n");
printf("8.删除第5号位置元素数据\n");
printf("0.退出\n");
printf("请选择你的操作：\n");
}
/////////////----------------------------------------------------------------//////////////////////////
int main(int argn, char* argv[], char* arge[])
{
//初始化L后：ListLength(L)=0
//1.查看链表
//2.创建链表(尾插法)
//3.链表长度
//4.中间结点值
//0.退出
//请选择你的操作：
LinkList linkHead = NULL;
int nSelect = -1;
ElemType e = 0, insert_e = 23, delsert_e;
if( InitList(&linkHead) )
{
printf("初始化L后：ListLength(L)=%d\n\n",ListLength(linkHead));
}
//输出界面
OutMenu();
//循环选择
while(1)
{
scanf("%d",&nSelect);
switch(nSelect)
{
case 1:
// printf("查看链表\n");
PrintList(linkHead);
break;
case 2:
printf("整体创建L元素(尾插法):\n");
CreateListTail(&linkHead,20);
break;
case 3:
// printf("链表长度\n");
printf("ListLength(L)=%d\n",ListLength(linkHead));
break;
case 4:
// printf("中间结点值\n");
GetMidNode(linkHead,&e);
printf("中间结点值:%d\n",e);
break;
case 5:
ClearList(&linkHead);
printf("ListLength(L)=%d\n",ListLength(linkHead));
break;
case 6:
OverList(&linkHead);
break;
case 7:
ListInsert(&linkHead,3,insert_e);
PrintList(linkHead);
break;
case 8:
ListDelete(&linkHead,5,&delsert_e);
PrintList(linkHead);
break;
case 0:
printf("退出\n");
break;
default:
printf("无效的选择\n");
OutMenu();
}
if(nSelect == 0)
{
break; //跳出while循环
}
}
////////////////////////////////////////////////
// printf("\n");
// system("pause");
return 0;
}

复制代码

错误的地方还请各位鱼油指正~~~

SDULZY · 发表于 2016-2-20 18:12:06

谢谢分享！

账号		自动登录	找回密码
密码			立即注册

[技术交流] 线性表11的作业题

马上注册，结交更多好友，享用更多功能^_^