文档章节

数据结构:顺序表

小强零号
 小强零号
发布于 2015/05/06 15:32
字数 1357
阅读 105
收藏 4
/*
 * this c file is a implementation of linear list
 * author: John Woods
 * date: 2015/5/3
 * exclaim: anyone can use the file to any purpose
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define INIT_LEN 20
#define INCREMENT_SIZE 10
#define BOOL int    /* define boolean type */
#define TRUE 1
#define FALSE 0

/* linear list structure */
typedef struct LinearList {
    int * LL;
    int Length;
    int MaxLength;
} * LinearList;

/* menu */
void menu();
void insert(LinearList myLL);
void delete(LinearList myLL);
void prior(LinearList myLL);
void next(LinearList myLL);
void current(LinearList myLL);

/* operations */
LinearList initList();    /* initial the linear list */
void destroyList(LinearList * p_myLL);    /* destroy the linear list, the linear list must be exist */
void clearList(LinearList myLL);    /* clear the linear list, the linear list must be exist */
BOOL listEmpty(LinearList myLL);    /* if linear list is empty, return TRUE, else return FALSE, and the linear list must be exist */
BOOL getElem(LinearList myLL, int index, int * cur_e);    /* return the value of list[i] in e, the linear list must be exist and i must between 0 and list.length-1 */
BOOL priorElem(LinearList myLLL, int index, int * pre_e);    /* return the prior element of the list[i], the linear list must be exist */
BOOL nextElem(LinearList myLL, int index, int * next_e);    /* return the next element of the list[i], the linear list must be exist */
void listInsert(LinearList myLL, int index, int e);    /* insert a element of e int position of i, the linear list must be exist and the i must between 0 and list.length */
BOOL listDelete(LinearList myLL, int index, int * e);    /* delete the element in position i, and return its value in e, the linear list must be exist */
void listTraverse(LinearList myLL);    /* traverse the list with the function visit() */

BOOL listExist(LinearList myLL);
void myflush();

int main(void) {
    int instruct = 0;
    LinearList myLL = NULL;
    
    while(TRUE) {
        menu();
        while(!scanf("%d", &instruct));
        switch(instruct) {
            case 1:
                myLL = initList();
                myLL->Length = 0;
                myLL->MaxLength = INIT_LEN;
                break;
            case 2:
                listTraverse(myLL);
                break;
            case 3:
                insert(myLL);
                break;
            case 4:
                delete(myLL);
                break;
            case 5:
                prior(myLL);
                break;
            case 6:
                next(myLL);
                break;
            case 7:
                current(myLL);
                break;
            case 8:
                clearList(myLL);
                break;
            case 9:
                destroyList(&myLL);
                break;
            default:
                exit(EXIT_SUCCESS);
                break;
        }
    }
    return 0;
}

void menu() {
    printf("Please choose your operation:\n");
    printf("\t| 1.initial a linear list    2.traverse the list\n");
    printf("\t| 3.insert an element        4.delete an element\n");
    printf("\t| 5.get the prior element    6.get the next element\n");
    printf("\t| 7.get an element           8.clear the linear list\n");
    printf("\t| 9.destroy the linear list  0.exit\n");
    printf("Give me your choice:");
}

void insert(LinearList myLL) {
    int index, e;
    char c,GoOn;
    if(FALSE == listExist(myLL)) {
        printf("Please initial the linear list first!\n");
        return;
    }
    while(TRUE)
    {
        //while('\n'!=(c=getchar()) && EOF!=c);    //clear the stdin stream
        printf("Input the insert position:");
        while(!scanf("%d", &index));
        while('\n'!=(c=getchar()) && EOF!=c);    //clear the stdin stream
        printf("Input the insert value:");
        while(!scanf("%d", &e));
    
        listInsert(myLL, index, e);
        
        while('\n'!=(c=getchar()) && EOF!=c);    //clear the stdin stream
        printf("Go on?(y/n) ");
        GoOn = getchar();
        if(GoOn != 'y' && GoOn != 'Y' && GoOn != '\n')    break;
    }
}

void delete(LinearList myLL) {
    int index, e;
    char c, GoOn;
    if(FALSE == listExist(myLL)) {
        printf("Please initial the linear list first!\n");
        return;
    }
    while(TRUE) {
        while('\n'!=(c=getchar()) && EOF!=c);    //clear the stdin stream
        printf("Please input the index for delete: ");
        scanf("%d", &index);
        if(listDelete(myLL, index, &e)) {
            printf("The deleted value is %d\n", e);
        }
        
        while('\n'!=(c=getchar()) && EOF!=c);    //clear the stdin stream
        printf("Go on?(y/n) ");
        GoOn = getchar();
        if(GoOn != 'y' && GoOn != 'Y' && GoOn != '\n')    break;
    }
    
}

void prior(LinearList myLL) {
    int index, pre_e;
    char c;
    if(FALSE == listExist(myLL)) {
        printf("Please initial the linear list first!\n");
        return;
    }
    while('\n'!=(c=getchar()) && EOF!=c);    //clear the stdin stream
    printf("Please input the index: ");
    scanf("%d", &index);
    if(priorElem(myLL, index, &pre_e)) {
        printf("The value before position %d is %d\n", index, pre_e);
    }
}

void next(LinearList myLL) {
    int index, next_e;
    char c;
    if(FALSE == listExist(myLL)) {
        printf("Please initial the linear list first!\n");
        return;
    }
    while('\n'!=(c=getchar()) && EOF!=c);    //clear the stdin stream
    printf("Please input the index: ");
    scanf("%d", &index);
    if(nextElem(myLL, index, &next_e)) {
        printf("The value after position %d is %d\n", index, next_e);
    }
}

void current(LinearList myLL) {
    int index, cur_e;
    char c;
    if(FALSE == listExist(myLL)) {
        printf("Please initial the linear list first!\n");
        return;
    }
    while('\n'!=(c=getchar()) && EOF!=c);    //clear the stdin stream
    printf("Please input the index: ");
    scanf("%d", &index);
    if(getElem(myLL, index, &cur_e)) {
        printf("The value in position %d is %d", index, cur_e);
    }
}

LinearList initList() {
    LinearList myLL = (LinearList)malloc(sizeof(struct LinearList));
    if(NULL == myLL) {
        printf("ERROR:Out of memeory\n");
        exit(EXIT_FAILURE);
    }
    myLL->LL = (int *)malloc(sizeof(int) * INIT_LEN);
    if(NULL == myLL->LL) {
        printf("ERROR:Out of memory\n");
        exit(EXIT_FAILURE);
    }
    
    printf("The linear list has been initialized\n");
    return myLL;
}

void destroyList(LinearList * p_myLL) {
    if(FALSE == listExist(*p_myLL)) {
        printf("Please initial the linear list first!\n");
        return;
    }
    free((*p_myLL)->LL);
    (*p_myLL)->LL = NULL;
    free(*p_myLL);
    *p_myLL = NULL;
    printf("The list has been destroyed!\n");
}

void clearList(LinearList myLL) {
    if(FALSE == listExist(myLL)) {
        printf("Please initial the linear list first!\n");
        return;
    }
    if(FALSE == listEmpty(myLL)) {
        myLL->Length = 0;
        printf("Clear operation is successful!\n");
    }
}

BOOL listEmpty(LinearList myLL) {
    if(0 == myLL->Length) {
        return TRUE;
    }else {
        return FALSE;
    }
}

BOOL getElem(LinearList myLL, int index, int * cur_e) {
    if(index <= myLL->Length && index >= 1) {
        *cur_e = *(myLL->LL + index - 1);
        return TRUE;
    }else {
        printf("You got wrong index!\n");
        return FALSE;
    }
}

BOOL priorElem(LinearList myLL, int index, int * pre_e) {
    if(index > myLL->Length || index <= 1) {
        printf("You got wrong index!\n");
        return FALSE;
    }else {
        *pre_e = *(myLL->LL + index - 2);
        return TRUE;
    }
}

BOOL nextElem(LinearList myLL, int index, int * next_e) {
    if(index >= myLL->Length || index <1) {
        printf("You got wrong index!\n");
        return FALSE;
    }else {
        *next_e = *(myLL->LL + index);
        return TRUE;
    }
}

void listInsert(LinearList myLL, int index, int e) {
    int i;
    if((myLL->Length+1)>myLL->MaxLength) {
        myLL->LL = (int *)realloc(myLL->LL,sizeof(int) * (myLL->MaxLength + INCREMENT_SIZE));
        myLL->MaxLength += INCREMENT_SIZE;
    }
    if(index > myLL->Length+1 || index<1) {
        printf("You got wrong position!\n");
        return;
    }else {
        for(i=myLL->Length-1; i>=index-1; i--) {
            *(myLL->LL + i + 1) = *(myLL->LL + i);
        }
        *(myLL->LL + index - 1) = e;
        myLL->Length++;
        printf("Insert operation is successful!\n");
    }
}


BOOL listDelete(LinearList myLL, int index, int * e) {
    int i;
    if(index > myLL->Length || index < 1) {
        printf("You got wrong index!\n");
        return FALSE;
    }else {
        *e = *(myLL->LL + i - 1);
        for(i = index-1; i < myLL->Length-1; i++) {
            *(myLL->LL + i) = *(myLL->LL + i + 1);
        }
        myLL->Length--;
        printf("Delete operation is successful!\n");
        return TRUE;
    }
}

void listTraverse(LinearList myLL) {
    int i;
    if(FALSE == listExist(myLL)) {
        printf("Please initial the linear list first!\n");
        return;
    }
    printf("Length of the linear list  is %d\n", myLL->Length);
    printf("Its elements are following:\n\t");
    printf("HEAD->");
    for(i=0; i<myLL->Length; i++) {
        printf("%d->", *(myLL->LL + i));
    }
    printf("END\n");
}

BOOL listExist(LinearList myLL) {
    if(NULL == myLL) return FALSE;
    else return TRUE;
}

因为代码在ubuntu环境下编写!在实现的过程中,发现无法用fflush(stdin)清空输入缓冲区,经过查看资料,发现fflush()并不是标准库函数,它的行为也就是未定义的!

fflush(stdin);    /* 该函数非标准库函数,行为未定义,使用此函数会牺牲代码的可移植性 */
while('\n'!=(c=getchar()) && EOF!=c);      /* 清空输入缓冲区的替代语句 */




© 著作权归作者所有

上一篇: 数据结构:链表
下一篇: html和htm的区别
小强零号
粉丝 6
博文 31
码字总数 12473
作品 0
长宁
程序员
私信 提问
数据结构/算法——线性表*

线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的。线性表的逻辑结构简单,...

cjun1990
2015/09/24
83
0
线性表Linear List-线性表的顺序表示和实现

线性表Linear List 线性表:线性表(Linear List)是由n(n≥0)个数据元素(结点)a[0],a[1],a[2]…,a[n-1]组成的有限序列 其中: 数据元素的个数n定义为表的长度 = "list".length() ("...

秋风醉了
2014/05/04
95
0
.NET Core 数据结构与算法 1-1

.NET Core 数据结构与算法 1-1 本节内容为顺序表 简介 线性表是简单、基本、常用的数据结构。线性表是线性结构的抽象 (Abstract),线性结构的特点是结构中的数据元素之间存在一对一的线性关系...

WarrenRyan
08/12
0
0
线性表

1、线性表的定义 线性表(List):零个或多个数据元素的有限序列 第一个元素无前驱,最后一个元素无后继,其他元素都有且只有一个前驱和后继。然后,线性表强调是有限的, 线性表元素的个数n...

DWade_Coding
2017/11/08
0
0
数据结构(java版)学习笔记(一)——线性表

一、线性表的定义 线性表是n(n>=0)个具有相同特性的数据元素的有限序列。 线性表是最简单、最常用的一种数据结构 线性表属于线性结构的一种 如果一个数据元素序列满足: (1)除第一个和最...

Stars-one
2018/07/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

CentOS7.6中安装使用fcitx框架

内容目录 一、为什么要使用fcitx?二、安装fcitx框架三、安装搜狗输入法 一、为什么要使用fcitx? Gnome3桌面自带的输入法框架为ibus,而在使用ibus时会时不时出现卡顿无法输入的现象。 搜狗和...

技术训练营
昨天
5
0
《Designing.Data-Intensive.Applications》笔记 四

第九章 一致性与共识 分布式系统最重要的的抽象之一是共识(consensus):让所有的节点对某件事达成一致。 最终一致性(eventual consistency)只提供较弱的保证,需要探索更高的一致性保证(stro...

丰田破产标志
昨天
8
0
docker 使用mysql

1, 进入容器 比如 myslq1 里面进行操作 docker exec -it mysql1 /bin/bash 2. 退出 容器 交互: exit 3. mysql 启动在容器里面,并且 可以本地连接mysql docker run --name mysql1 --env MY...

之渊
昨天
10
0
python数据结构

1、字符串及其方法(案例来自Python-100-Days) def main(): str1 = 'hello, world!' # 通过len函数计算字符串的长度 print(len(str1)) # 13 # 获得字符串首字母大写的...

huijue
昨天
6
0
PHP+Ajax微信手机端九宫格抽奖实例

PHP+Ajax结合lottery.js制作的一款微信手机端九宫格抽奖实例,抽奖完成后有收货地址添加表单出现。支持可以设置中奖概率等。 奖品列表 <div class="lottery_list clearfix" id="lottery"> ......

ymkjs1990
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部