论坛 › 数据结构与算法 › 线性表11的作业题

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

线性表11的作业题

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

#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;
}




错误的地方还请各位鱼油指正~~~{:9_226:}

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

谢谢分享！

查看完整版本: 线性表11的作业题