【自考】数据结构中的线性表，期末不挂科指南，第2篇

const int Maxsize = 100 ;  // 预先定义一个足够大的常数
typedef struct{
    DataType data[Maxsize]; // 存放数据的数组
    int length ; // 顺序表的实际长度
} SeqList; // 顺序表类型名为SeqList  
SeqList L ;  // 定义一个L为顺序表

#include <stdio.h>
#include <stdlib.h>

const int Maxsize = 10;
typedef struct SeqList{
    int *data; //一个int指针，后面用来初始化数组用
    int length;
} seq;

// 顺序表的初始化函数
seq init(){
    seq s;
    s.data = (int*)malloc(Maxsize*sizeof(int)); // 构造一个空的顺序表，动态申请存储空间
    if(!s.data) // 如果申请失败，退出程序
    {
        printf("初始化失败");
        exit(0);
    }
    s.length = 0; // 空表的长度初始化为0
    return s;
}

void display(seq s){
    for(int i=0;i<s.length;i++){
        printf("%d",s.data[i]);
    }
    printf("\n");
    
}

int main()
{
    seq s = init();
    //添加一个元素进入
    for(int i=1;i<=5;i++){
        s.data[i-1] = i;
        s.length++;
    }
    printf("初始化之后，表的数据为:\n");
    display(s);

    return 0;
}

seq delete_seq(seq s,int i){
    if(i<1||i>s.length){
        printf("位置错误");
        exit(0);
    }
    
    // 第i个元素下标修改为i-1
    for(int j=i;j<s.length;j++){
        s.data[j-1] = s.data[j];
    }
    
    s.length--;
    return s;
}

// 注意，这个地方需要返回的为int了，也就是位置
int locate(seq s,int x){
    int i =0;
    while((i<s.length)&&(s.data[i]!=x)){
        i++;
    }
    if(i<s.length) return i+1;
    else return -1;
}

//链表中的每个结点的实现
//包含数据域与指针域
typedef struct node{
    int data;// 数据域，为了计算方便，类型设置为数字
    struct node *next; // 指针域，指向后继元素
} Node,*LinkList;

// 初始化
LinkList init(){
    Node *L; // 定义一个头结点
    L =(LinkList)malloc(sizeof(Node)); //头结点申请地址
    if(L == NULL){
        printf("初始化失败!\n");
        exit(0);
    }
    L->next =NULL;
    return L;
}

// 头插入法
void insert_head(Node *L){
    int i,n,num;  // n表示元素的个数 
    Node *pnew;
    printf("请输入要插入的元素个数：n = ");
    scanf("%d",&n);
    for(i=0;i<n;i++){
        printf("请输入第%d个元素： ",i+1);
        scanf("%d",&num);
        pnew = (LinkList)malloc(sizeof(Node));
        pnew->data = num; // 将数字存储到数据域
        pnew->next = L->next; // 指针域指向L（头结点）的指针域
        L->next = pnew; // 头结点指针域指向新结点地址
        
    }
}

// 尾插法
void insert_tail(Node *L){
    int i,n,num;
    Node *p,*pnew;
    p = L;
    
    printf("要输入元素的个数：n = ");
    scanf("%d",&n);
    for(i=0;i<n;i++){
        
        printf("请输入第%d个元素：",i+1);
        scanf("%d",&num);
        pnew = (LinkList)malloc(sizeof(Node));
        if(pnew == NULL){
            printf("初始化失败");
            exit(0);
        }
        pnew->data = num;
        p->next = pnew;
        p = pnew;
        
    }
    p->next = NULL;
  
}

//求表长
int get_length(LinkList L){
    LinkList p;
    int length = 0;
    p = L->next;   // p 指向第一个结点
    while(p){
        printf("单链表的数据为%d\n",p->data);
        length++;
        p = p->next;
    }
    return length;
}

// 读表中的元素
LinkList get_element(LinkList L,int i){
    // 在单链表L中查找第i个结点，若找到，则返回指向该结点的指针，否则返回NULL
    Node *p;
    p = L->next;
    int position = 1;
    while((position<i)&&(p!=NULL)){ // 当未到第i结点且未到尾结点时继续后移
        p = p->next;
        position++;
    }
    if(i==position) return p; //找到第i个结点
    else return NULL;   // 查找失败
}

int get_element_by_data(LinkList L,int x){
    Node *p;
    p = L->next;
    int i = 0;
    while(p!=NULL && p->data == x){
        p = p->next;
        i++;
    }
    if (p!=NULL) return i+1;
    else return 0;
}

/在任意位置插入元素，x为要插入的内容，i为插入的位置
void insert(LinkList L,int x,int i){
    
    Node *p,*q; //p表示要插入的元素，q表示要被插入的元素
    if(i==1) q = L; //如果i==1,那么p=L进行初始化操作
    else q = get_element(L,i-1); // 找到第i-1个元素
    
    if(q==NULL){
        printf("找不到位置");
        exit(0);
    }
    else{
         p =(LinkList)malloc(sizeof(Node));
         p->data = x;
         p->next = q->next; // 新生成的p指向q的下一个结点
         q->next = p;//q的指针域指向新生成的p
        
    }
}

// p表示的是待删除的结点
p->prior->next = p->next;
p->next->prior = p->prior;
free(p)

t->prior = p;
p->next = t;  // 这两个步骤将t和p连接起来了

t->next = p->next;
p->next->prior = t; //这两个步骤将t和p后继结点连接起来了