一、     实验目的

 掌握线性表的顺序表和链表的基本操作：建立、插入、删除、查找、合并、打印等运算。

一、  源程序

顺序表：

#include<iostream>
using namespace std;
#define OK 1
#define OVERFLOW -1
#define ERROR 0
#define MAXSIZE 100
int typedef Status;
typedef struct//定义结构体
{
    int *elem;
    int length;
}SqList;
Status InitList(SqList &L)//顺序表的初始化
{
    L.elem = new int[MAXSIZE];//分配一个数组空间
    if (!L.elem)exit(OVERFLOW);
    L.length = 0;
    return OK;
}
Status GetElem(SqList L, int i, int &e)//顺序表的取值
{
    if (i<1 || i>L.length)return ERROR;
    e = L.elem[i - 1];//[i-1]存储大第[i]个元素
    return OK;
}
int LocateElem(SqList L, int e)//查找
{
    for (int i=0; i < L.length; i++)
    {
        if (L.elem[i] == e)return i + 1;
    }
    return 0;
}
Status ListInsert(SqList &L, int i, int e)//插入
{
    if ((i<1) || (i>L.length + 1))return ERROR;
    if (L.length == MAXSIZE)return ERROR;
    for (int j = L.length - 1; j>i - 1; j--)
    {
        L.elem[j + 1] = L.elem[j];
    }
    L.elem[i - 1] = e;
    ++L.length;
    return OK;
}
Status ListDelete(SqList &L, int i)//删除
{
    if ((i<1) || (i>L.length))return ERROR;
    for (int j = i; j < L.length - 1; j++)
    {
        L.elem[j - 1] = L.elem[j];//是第i个但在数组里是第i-1个
    }
    --L.length;
    return OK;
}
void MergeList_Sq(SqList LA, SqList LB, SqList &LC)//有序表的合并
{
    LC.length = LA.length + LB.length;
    LC.elem = new int[LC.length];
    int *pc = LC.elem;
    int *pa = LA.elem;
    int *pb = LB.elem;
    int *pa_last = LA.elem + LA.length - 1;//指向最后一个元素
    int *pb_last = LB.elem + LB.length - 1;
    while ((pa <= pa_last) && (pb <= pb_last))
    {
        if ((pa <= pa_last) && (pb <= pb_last))
        
            if (*pa <= *pb) *pc++ = *pa++;
            else *pc++ = *pb++;
        
        
    }
        while (pa <= pa_last)*pc++= *pa++;
        while (pb <= pb_last)*pc++ = *pb++;
    
}
int main()
{
    SqList N, M;
    InitList(N);
    InitList(M);
    cout << "请输入第一个数组的长度" << endl;;
    cin >> N.length;
    cout << "请依次输入1到" << N.length << "的数据" << endl;
    for (int i = 0; i < N.length; i++)
    {
        cin >> N.elem[i];
    }
    cout << "请输入第二个数组的长度" << endl;;
    cin >> M.length;
    cout << "请依次输入1到" << M.length << "的数据" << endl;
    for (int i = 0; i < M.length; i++)
    {
        cin >> M.elem[i];
    }
    SqList A;
    MergeList_Sq(N, M, A);
    for (int i = 0; i < A.length; i++)
    {
        cout << A.elem[i] << endl;
    }
}

约瑟夫退圈

  1 #include<iostream>
  2 using namespace  std;
  3 #define OK 1
  4 #define OVERFLOW -1
  5 #define ERROR 0
  6 #define MAXSIZE 100
  7 int typedef Status;
  8 typedef struct LNode//循环链表定义
  9 {
 10     int data;
 11     int num;
 12     struct LNode *rear;
 13 }LNode,*LinkList;
 14 Status InitList(LinkList &L)//循环链表初始化
 15 {
 16     L = new LNode;
 17     L->rear = L;
 18     L->num = 0;
 19     return OK;
 20 }
 21 Status GetElem(LinkList L, int i, int &e)//取值
 22 {
 23     LNode *p = L->rear; int j = 1;
 24     while (p&&j < i)//是否要有p
 25     {
 26         p = p->rear;
 27         ++j;
 28     }
 29     if (!p || j>i)return ERROR;
 30     e = p->data;
 31     return OK;
 32 }
 33 LNode *LocateElem(LinkList L, int e)//查找
 34 {
 35     LNode *p = L->rear;
 36     while (p&&p->data != e)//是否要有p
 37     {
 38         p = p->rear;
 39     }
 40     return p;
 41 }
 42 Status LisrInsert(LinkList &L, int i, int e)//插入
 43 {
 44     LNode *p = L; int j = 0;
 45     while (p && (j < i - 1))
 46     {
 47         p = p->rear;
 48         ++j;
 49     }
 50     if (!p || j>i - 1)return ERROR;
 51     LNode *s = new LNode;
 52     s->data = e;
 53     s->rear = p->rear;
 54     p->rear = s;
 55     return OK;
 56 }
 57 Status ListDelete(LinkList &L, int i)//删除
 58 {
 59     LNode*p = L; int j = 0;
 60     while ((p->rear) && (j < i - 1))
 61     {
 62         p = p->rear; ++j;
 63     }
 64     if ( (j>i - 1))return ERROR;
 65     LNode *q = p->rear;
 66     p->rear = q->rear;
 67     delete q;
 68     return OK;
 69 }
 70 int main()
 71 {
 72     LinkList N;
 73     LNode *t = NULL, *head;
 74     InitList(N);
 75     head = N->rear;
 76     int n;
 77     int A[MAXSIZE];
 78     cout << "请输入有几名学生：" << endl;
 79     cin >> n;
 80     int j = 0,i,a=0;
 81     while (j < n)
 82     {
 83         A[a] = (a + 1);        
 84         cout <<"第"<<A[a]<< "人，请输入密码：" << endl;
 85         cin >> i;
 86         t = new LNode;
 87         t->data = i;
 88         t->rear = N;
 89         head->rear = t;
 90         head = t;
 91         ++j;
 92         ++a;
 93         ++t->num;
 94     }
 95     cout << "约瑟夫环的人数以及对应密码分别是：" << endl;
 96     j = 0;
 97     head = N->rear;
 98     while (j<n)
 99     {
100         cout << "第" << A[j] << "个人，密码" << head->data << endl;
101         head = head->rear;
102         ++j;
103     }
104     cout << "请输入您想要从几开始删除：" << endl;
105     int m; cin >> m;
106     //N = N->rear;
107     ListDelete(N, m);
108     j = 0;
109     while (j<n)
110     {
111         cout << "第" << A[j] << "个人，密码" << head->data << endl;
112         head = head->rear;
113         ++j;
114     }
115     }