【数据结构】之 线性表详解(2)

【算法描述】顺序表的删除运算

//删除 
int deleteList(List *L,char *content){
    int k;
    
    //删除位置不合法则推出 
    if(i < 0 || (i >= L->len)){
        printf("删除位置不合法！\n\n");
        return ERROR;
    }
    
    //删除的表已空 
    if(L->len == 0){
        printf("表已空！\n\n");
        return ERROR;
    }else{
        *content = L->data[i];
        
        //前移 
        for(k = i; k <= L->len - 2; k++){
            L->data[k] = L->data[k+1];
        }
        
        //删除成功后表长度减一 
        L->len--;
        printf("删除成功！\n\n");
        print(L);
        return OK;
    }
}?

小结：与插入算法类似，删除运算也要移动结点。设E为删除一个元素所需移动元素的平均移动次数， 为 删除第i个元素的概率，并假设在任何位置上删除的概率相等，即 ，i=1，2，……，n 。则有：

最后的汇总代码如下：

/*
线性表的顺序存储 
基本操作：查找，插入，删除 
*/

#include<stdio.h>
#include<string.h>

#define MAXSIZE 100             
#define OK 1
#define ERROR -1

typedef struct{
    char data[MAXSIZE];    
    int len;    //数据长度 
}List;

List* initList(List *L);                                                    //初始化 
int getAsNum(List L,int num);                                        //按序号查找 
int getAsContent(List L,char content);                        //按内容查找
int insertList(List *L,char content);            //插入，在元素之前插入        
int deleteList(List *L,char *content);        //删除
void print(List *L);                                                            //打印

//初始化顺序表 
List* initList(List *L){
    int num,&ch);
        L->data[i] = ch;
    }
    return L;
}

//按序号查找 
int getAsNum(List L,int num){
    if(num < 0 || num > L.len - 1){
        printf("查找失败，位置 %d 超过链表长度！\n\n",num);
        return ERROR;
    }else{
        printf("按序号查找成功，第 %d 个位置元素为 %c \n\n",num,L.data[num]);
        return num;
    }
}

//按内容查找
int getAsContent(List L,L.data[i]);
        return i;
    }else{
        //未找到 
        printf("查找失败，没有你所找的元素！\n\n");
        return ERROR; 
    }
}

//插入，在元素之前插入
int insertList(List *L,char content){
    int k;
    
    //插入的位置不在表的范围 
    if(i < 0 || i >= L->len){
        printf("插入位置不合法！\n\n");
        return ERROR;
    }
    
    //考虑表满的情况 
    if(L->len == MAXSIZE){
        printf("表已满！无法插入！\n\n");
        return ERROR;
    }else if(i >= 0 && i <= L->len - 1){
        
        //插入位置后的元素向后移动 
        for(k = L->len - 1; k >= i; k--){
            L->data[k+1] = L->data[k];
        }
        L->data[i] = content;
        //表长度加一 
        L->len++;
        printf("插入成功！\n\n");
        print(L);
        return OK;
    }
} 

//删除 
int deleteList(List *L,char *content){
    int k;
    
    //删除位置不合法则推出 
    if(i < 0 || (i >= L->len)){
        printf("删除位置不合法！\n\n");
        return ERROR;
    }
    
    //删除的表已空 
    if(L->len == 0){
        printf("表已空！\n\n");
        return ERROR;
    }else{
        *content = L->data[i];
        
        //前移 
        for(k = i; k <= L->len - 2; k++){
            L->data[k] = L->data[k+1];
        }
        
        //删除成功后表长度减一 
        L->len--;
        printf("删除成功！\n\n");
        print(L);
        return OK;
    }
}

//打印 
void print(List *L){
    int i; 
    printf("===================顺序表如下===================\n");
    printf("共有 %d 个数据: ",L->len); 
    for(i = 0; i < L->len; i++){
        printf("%c ",L->data[i]);
    }
    printf("\n");
}

int main(void){
    List L;
    int i,length,flag = 1;
    char ch,cha; 
    
    //初始化 
    initList(&L); 
    print(&L);
    
    //按序号查找 
    printf("请输入你要查找的元素序号：");
    scanf("%d",&num);
    getchar();
    getAsNum(L,num);
    
    //按内容查找 
    printf("请输入你要查找的元素的内容：");
    scanf("%c",&ch);
    getchar();
    getAsContent(L,ch);
    
    //插入元素 
    printf("请输入你要插入的内容(格式:addr_num data_char)：");
    scanf("%d %c",&num,&ch);
    getchar();
    insertList(&L,ch);
    
    //删除元素 
    printf("请输入你要删除的位置(格式:addr_num)：");
    scanf("%d",&num);
    getchar();
    deleteList(&L,&cha);    
    
    return 0;
} 

?

执行结果：

??

线性表的链式存储

链表：链表使用一组任意的存储单元来存放线性表的结点，这组存储单元可以是连续的，也可以是非连续的，甚至是零散分布在内存的任何位置。

采用链式存储结构的线性表称为线性链表。从链接方式看，链表可分为单链表，循环链表，双链表（也叫循环双链表，双向链表）。从实现角度看可分为动态链表和静态链表。

结点：结点包括两个域：数据域和指针域。数据域存放数据，指针域指向其他结点的地址。两个域的数量视具体情况而定。

单链表和循环单链表有一个指针域，双链表有连个指针域。

单链表

单链表中每个结点的存储地址存放在其前驱结点的指针域中，由于线性表的第一个结点无前驱，通常设一个头指针header指向第一个结点。

（编辑：ASP站长网）