顺序表的一些记录和练习

typedef struct{
    int data[MaxSize]; //用静态的数组存放数据元素
    int length; //顺序表的当前长度
}SqList; //顺序表的类型定义

//基本操作---初始化一个线性表
void InitList(SqList &L){
    for(int i=0;i<MaxSize;i++){
        L.data[i] = 0; //将所有数据置为零
    L.length=0;
    }
}
int main(){
    SqList L; //声明一个顺序表
    InitList(L); //初始化
    //后续操作
    return 0;
}

//动态分配
#define InitSize 10
typedef struct{ 
    int *data; 
    int MaxSize,length;
}SeqList;

void InitList(SeqList &L){
    L.data=(int*)malloc(InitSize*sizeof(int));
    L.length=0;
    L.MaxSize=InitSize;
    }
}

//增加动态数组的长度
void IncreaseSize(SeqList &L,int len){
    int *p = L.data;
    L.data = (int*)malloc((L.MaxSize+len)*sizeof(int));
    for (int i = 0; i < L.length; i++)
    {
        L.data[i] = p[i];
    }
    L.MaxSize = L.MaxSize+len;
    free(p);
}

int main(){
    SeqList L; //声明一个顺序表
    InitList(L); //初始化
    //后续操作
    IncreaseList(L,5);
    return 0;
}

//插入操作
ListInsert(&L,i,e);

bool ListInsert(&L,int i,int e){
    if(i<1||i>L.length+1)
       return false;
    if(L.length>=MaxSize)
       return false;
    for(int j = L.length;j >= i;j--){
        L.data[j] = L.data[j-1];
    }
    L.data[i-1] = e;
    L.length++;
    return true;
}

//删除操作

bool ListDelete(SqList &L,int i,int &e){
    if(i<1||i>L.length)
        return false;
    e = L.data[i-1];
    for (int j=i; j < L.length;j++)
    {
        L.data[j-1] = L.data[j];
    }
    L.length--;
    return true;
}

//从顺序表删除最小的元素，并返回最小元素,由最后一个元素填补

bool Del_Min(SqList &L,int &value){
    if(L.length == 0)
        return false;
    value = L.data[0];
    int pos = 0;
    for(i=1;i<L.length;i++){
        if(value>L.data[i]){
            value = L.data[i];
            pos = i;
        }
    }
    L.data[pos] = L.data[L.length-1];
    L.length--;
    return true;
}

//逆置顺序表

bool reverse(SqList &L){
    if(L.length == 0)
        return false;
    int temp;
    for(int i = 0;i < L.length/2;i++){
        temp = L.data[i];
        L.data[i] = L.data[L.length-i-1];
        L.data[L.length-i-1] = temp;
    }
    return true;
}

//删除指定值X

bool Del_value1(SqList &L，int x){
    int k = 0;
    for(i = 0; i < L.length;i++)
        if(L.data[i]!=x){
            L.data[k] = L.data[i];
            k++;
        }
    L.length = k;
}

bool Del_value2(SqList &L,int x){
    int k = 0,i = 0;
    while (i<L.length)
    {
        if(L.data[i] == x)
            k++;
        else
            L.data[i-k] = L.data[i];
        i++;
    }
    L.length = L.length-k;
    return true;
}

//删除s到t（包含s，t）

bool Del_s_t(SqList &L,int s,int t){
    if(L.length==0||s>=t)
        return false;
    for (int i = 0; i < L.length && L.data[i] < s; i++)
        if(i>=L.length)
            return false;
    for(int j = i; j < L.length && L.data[j] <= t; j++)
    for(;j<L.length;i++;j++)
        L.data[i] = L.data[j];
    L.length = L.length - (j - i);
    return true;
}

//删除重复的数

bool Del_mul(SqList &L){
    if(L.length == 0)
        return false;
    int k = 0;
    int value = L.data[0];
    for(int i = 1;i < L.length; i++){
        if(value != L.data[i]){
            value = L.data[i];
            L.data[i-k] = L.data[i];
        }
        else
            k++;
    }
    return true;
}

//合并两个有序顺序表

bool Merge_List(SqList A,SqList B,SqList &C){
    if (A.length+B.length>C.length)
    {
        return false;
    }
    int i=0,j=0,k=0;
    while (i<A.length&&j<B.length)
    {
        if (A.data[i]<=B.data[j])
            C.data[k++]=A.data[i++];
        else
            C.data[k++]=B.data[j++];
    }
    while (i<A.length)
        C.data[k++]=A.data[i++];
    while (j<B.length)
        C.data[k++]=B.data[j++];
    C.length=k;
    return true;
}

//编写一个函数，将数组中的两个线性表互换位置

void Reversal(int data[], int m, int n) {
    int temp;
    int k = 0;
    for (int i = 0; i < m / 2; i++) {  //反转第一个线性表
        temp = data[i];
        data[i] = data[m - i - 1];
        data[m - i - 1] = temp;
    }
    for (int j = m; j < (n + 2 * m) / 2; j++) { //反转第二个线性表
        temp = data[j];
        data[j] = data[m + n - k - 1];
        data[n + m - k - 1] = temp;
        k++;
    }
    for (int c = 0; c < (m + n) / 2; c++) { //整体反转数组
        temp = data[c];
        data[c] = data[m + n - c - 1];
        data[m + n - c - 1] = temp;
    }
}

//找主元素(不是最佳方法) 辅助数组中包含大量未使用空间
int Search_main(int data[], int n) {
    int value, ep[MaxSize];  //数组计数
    for (int i = 0; i < n; i++) {
        value = data[i];
        ep[value]++;
    }
    for (int j = 0; j < MaxSize; j++)
        if (ep[j] > n / 2)
            return j;
        else
            return -1;
    return -1;
}

//找未出现的最小正整数
#define max 10000
void Search_min(int data[], int n) {
    int ep[max], value;
    for (int i = 0; i < n; i++) {
        if (data[i] > 0) {
            value = data[i];
            ep[value]++;
        } else
            continue;
    }
    for (int j = 1; j < max; j++) {
        if (ep[j] == 0) {
            printf("%d", j);
            break;
        }
    }
}

#define MaxSize 50

//队列

typedef struct 
{
    int data[MaxSize];
    int front,rear;
}SqQueue;

//基本操作

//初始化队列
void InitQueue(SqQueue &Q){
    Q.front = Q.rear = 0;  //初始化队尾，队首指针
}
//判断是否队空
bool QueueEmpty(SqQueue Q){
    if(Q.front == Q.rear)
        return true;
    else
        return false;
}
//入队
bool EnQueue(SqQueue &Q, int x){
    if((Q.rear+1) == Q.front)
        return false;
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear+1)%MaxSize;
    return true;
}
//出队
bool DeQueue(SqQueue &Q, int &x){
    if(Q.front == Q.rear)
        return false;
    x = Q.data[front];
    Q.front = (Q.front+1)%MaxSize;
    return true;
}

//队列的链式储存
typedef struct //链式队列节点
{
    int data;
    struct LinkNode *next;
}LinkNode;

typedef struct{ //链式队列
    LinkNode *front,*rear; //头尾指针
}LinkQueue;

//初始化链队
void InitQueue(LinkQueue &Q){
    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode)); //建立头结点
    Q.rear->next = NULL;
}

//判队空
bool isEmpty(LinkQueue Q){
    if(Q.rear == Q.front)
        return true;
    else
        return false;
}

//入队
void EnQueue(LinkQueue &Q,int x){
    LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode)); //建立新节点
    s->data = x; //将值赋给新节点
    s->next = NULL; 
    Q.rear->next = s; //将新节点接到链表后
    Q.rear = s; //尾指针后移
}

//出队
bool DeQueue(LinkQueue &Q，int &x){
    if(isEmpty(LinkQueue Q)) //判断队空
        return false;
    LinkNode *p = Q.front->next; //p指针指向第一个节点
    x = p->data;                 //取得第一个节点数据
    Q.front->next = p->next;     //删除第一个节点
    if(Q.rear == p)              //若只有一个节点
        Q.rear = Q.front;
    free(p);
    return true;
}