数据结构：线性表

#include #include #include #include #define maxlenglth 1000#define OK 1#define ERROR 0using namespace std;typedef int Elemtype;typedef int Status;typedef int Position;struct SeqList{Elemtype data[maxlenglth];int lenth;};// 线性表的定义Status Display(SeqList L);//打 印SeqList InitList();// 初始化Position End(SeqList L); // 返回最后的位置Status Insert(Elemtype t, Position p, SeqList &L); // 在位置p插入元素tStatus Delete(Elemtype t, SeqList &L); //删除所有元素tStatus Sort(SeqList &L); //排序Status Unique(SeqList &L); //对排完序去重Status ReverseList(SeqList &L); //翻转（逆置）Status Merge(SeqList &L1, SeqList L2); //合并两个排好序的Status Move(SeqList &L, int flag, int step); //移动int main(){// basic testint n1, n2;SeqList L1 = InitList();SeqList L2 = InitList();cout <> n1;cout << "please input L1's data:" << "\n";for(int i = 1; i > x;Insert(x, L1.lenth + 1, L1);}Display(L1);cout << "----Delete----" <> temp;Delete(temp, L1);Display(L1);cout << "----Sorted----" << "\n";Sort(L1);Display(L1);cout << "----Uniqued----" << "\n";Unique(L1);Display(L1);// merge testcout <> n2;cout << "please input L2's data:" << "\n";for(int i = 1; i > x;Insert(x, L2.lenth + 1, L2);}Display(L2);cout << "----Merged----" << "\n";Merge(L1, L2);Display(L1);// move testint flag, step;cout <> flag;cout <> step;Move(L1, flag, step);Display(L1);cin >> n1;return 0;}Status Display(SeqList L){for(int i = 1; i <= L.lenth; i ++ ) cout << L.data[i] << " \n"[i == L.lenth];}SeqList InitList(){SeqList List;List.lenth = 0;return List;}Position End(SeqList L){return L.lenth;}Status Insert(Elemtype t, Position p, SeqList &L){if(L.lenth + 1 == maxlenglth){cout << "Full list!" < L.lenth + 1 || p < 1){cout << "Invalid Position!" < p; i -- ){L.data[i] = L.data[i - 1];}L.data[p] = t;return 0;}Status Delete(Elemtype t, SeqList &L){Position idx = 0; for(int i = 1; i <= L.lenth; i ++ ){if(L.data[i] != t){idx ++;L.data[idx] = L.data[i];}}L.lenth = idx;return 0;}Status Sort(SeqList &L){sort(L.data + 1, L.data + L.lenth + 1);return 0; }Status Unique(SeqList &L){Position idx = 0;Elemtype last = 0; for(int i = 1; i <= L.lenth; i ++){if(i == 1){last = L.data[i];idx ++;L.data[idx] = L.data[i];}else{if(last != L.data[i]){idx ++;L.data[idx] = L.data[i];last = L.data[i];}}}L.lenth = idx;return 0;}Status ReverseList(SeqList &L){for(int i = 1, j = L.lenth; i = maxlenglth){cout << "Overflow!" << "\n";return 1;}for(int i = L2.lenth + 1, j = 1; j <= L1.lenth; j ++ , i ++){L2.data[i] = L1.data[j];}Position idx = 0;Position i, j;for(i = 1, j = L2.lenth + 1; i <= L2.lenth && j <= L1.lenth + L2.lenth;){if(L2.data[i] <= L2.data[j]){idx ++;L1.data[idx] = L2.data[i];i ++;}else{idx ++;L1.data[idx] = L2.data[j];j ++;}}while(i <= L2.lenth){idx ++;L1.data[idx] = L2.data[i];i ++;}while(j <= L2.lenth + L1.lenth){idx ++;L1.data[idx] = L2.data[j];j ++;}L1.lenth += L2.lenth;return 0;}Status Move(SeqList &L, int flag, int step){static SeqList temp = InitList();temp.lenth = L.lenth;if(temp.lenth == 0){return 1;}for(int i = 1; i <= temp.lenth; i ++ ){temp.data[i] = L.data[i];}step = step % L.lenth;if(flag == 0){flag = 1;}else{flag = -1;}for(int i = 1; i  temp.lenth){j -= temp.lenth;}if(j < 1){j += temp.lenth;}L.data[j] = temp.data[i];}return 0;}

#include #include #include #include #include #define OK 0#define ERROR 1using namespace std;typedef int Elemtype;typedef int Status;struct Node{Elemtype data;Node * next;};//链表定义typedef Node * Position;typedef Node * LIST;void Creat(LIST head,int size);//创建 void ForwardInsert(LIST head,Elemtype x);//头插 void BackInsert(LIST head,int x);//尾插 void Travel(LIST head);//遍历 Status IsEmpty(LIST head);//判空 void AllDelete(LIST head);//删除 void SomeDataDelete(LIST head,Elemtype x);//删除一个数 void SomeDataInsert(LIST head,Elemtype x,int num);//在某位置插入一个数 void Sort(LIST head, int (*cmp)(Elemtype, Elemtype));//冒泡排序 int Ascend(Elemtype x, Elemtype y);//升序 int Descend(Elemtype x, Elemtype y);//降序 Position Locate(Elemtype x, LIST head);void Unique(LIST head);//去重Status Reverse(LIST head);//翻转Status Move(LIST head, int flag, int step);//循环移动Status Merge(LIST head1, LIST head2);//合并两个排好序的链表int Len(LIST head);//求链表长void MergeTest();//合并的测试int main(){LIST head = (LIST)malloc(sizeof(Node));//头节点 head->next = NULL;int num, i;Elemtype temp;cout <> num;Creat(head,num);Travel(head);cout <> temp;ForwardInsert(head,temp);Travel(head);cout <> temp;BackInsert(head,temp);Travel(head);cout <> temp;SomeDataDelete(head,temp);Travel(head);cout <> temp >> i;SomeDataInsert(head,temp,i);Travel(head);// 排序测试cout << "----Sorted----" << "\n";Sort(head,Descend);Travel(head);//去重测试cout << "----Uniqued----" << "\n";Unique(head);Travel(head);// 翻转测试cout << "----Reversed----" << "\n";Reverse(head);Travel(head);// 循环左(右)移测试cout << "----Move----" << "\n";int flag ,step;cout << "(right, left)(0,1)---(step)" <> flag >> step;Move(head, flag, step);Travel(head);// 合并测试MergeTest();AllDelete(head);Travel(head);free(head);//free掉头节点 return 0;}void MergeTest(){int num;cout << "----Merge----" <next = NULL;cout <> num;Creat(h1,num);Sort(h1, Descend);LIST h2 = (LIST)malloc(sizeof(Node));h2->next = NULL;cout <> num;Creat(h2,num);Sort(h2, Descend);Merge(h1, h2);cout << "Merged list:" <next, p2 = head2->next;LIST temp = head1;while(p1 != NULL && p2 != NULL){if(p1->data data){temp->next = p1;p1 = p1->next;}else{temp->next = p2;p2 = p2->next; }temp = temp->next;}while(p1 != NULL){temp->next = p1;p1 = p1->next;temp = temp->next;}while(p2 != NULL){temp->next = p2;p2 = p2->next;temp = temp->next;}temp->next = NULL;return OK;}Status Move(LIST head, int flag, int step){int len = Len(head);step = step % len;if(step == 0){return OK;}if(flag == 0){step = len - step;}LIST p, q, s;p = q = s = head;p = p->next;int idx = 0;while(s->next != NULL){idx ++;s = s->next;if(idx == step){q = s;}}head->next = q->next;s->next = p;q->next = NULL;return OK;}int Len(LIST head){LIST p = head;int cnt = 0;while(p->next != NULL){cnt ++;p = p->next;}return cnt;}void Unique(LIST head){Elemtype last;LIST p, q;p = head->next;if(p == NULL || p->next == NULL){return;}last = p->data;q = p->next;while(q != NULL){if(q->data == last){p->next = q->next;free(q);if(p->next == NULL){q = NULL;}else{q = p->next;}}else{last = q->data;q = q->next;p = p->next;}}}Status Reverse(LIST head){LIST p, q, s;p = q = s = head->next;q = p->next;while(q != NULL){p->next = q->next;q->next = s;s = q;q = p->next;}head->next = s;return OK;}Position Locate(Elemtype x, LIST head){Position p = head;while(p->next != NULL){if(p->data == x){return p;}else{p = p->next;}}return p;/* 如果没有找到 */}int Descend(Elemtype x, Elemtype y){return x > y;}int Ascend(Elemtype x, Elemtype y){return x next == NULL){cout <next->next==NULL){cout <next; p1->next != NULL; p1 = p1->next)  {  for (p2 = p1->next; p2!=NULL; p2 = p2->next)  {  if ((*cmp)(p1->data, p2->data))  {swap(p1->data, p2->data);   }  } }}void Creat(LIST head, int size){LIST p = head;for(int i = 1;i next = NULL;cin >> newnode->data;p->next = newnode;p = newnode;}}void ForwardInsert(LIST head, Elemtype x){LIST newhead = (LIST)malloc(sizeof(Node));newhead->data = x;newhead->next = head->next;head->next = newhead;return;}void Travel(LIST head){LIST p = head;while(p->next != NULL){p = p->next; cout <data << " ";}cout <next = NULL;back->data = x;while(p->next != NULL){p = p->next;}p->next = back;return;}Status IsEmpty(LIST head){if(head->next == NULL){cout << "is Empty!" << "\n";return OK;}else{cout << "not Empty!" <next;LIST temp = head;while(p != NULL){temp = p;p = p->next;free(temp);}head->next = NULL;return;}void SomeDataDelete(LIST head, Elemtype x){LIST p = head->next;LIST last = head;LIST temp = NULL;while(p != NULL){if(temp != NULL){free(temp);temp = NULL;}if(p->data == x){last->next = p->next;temp = p;}else{last = last->next;}p = p->next;}return;}void SomeDataInsert(LIST head,Elemtype x,int num){LIST p = head;LIST last = head;int idx = 0;while(p->next != NULL){p = p->next;idx ++;if(idx == num){LIST NewNode = (LIST)malloc(sizeof(Node));NewNode->data = x;last->next = NewNode;NewNode->next = p;}last = last->next;}}

#include #include #include #include #define OK 1#define ERROR 0#define MAXSIZE 1000 using namespace std;typedef int Status;       typedef int ElemType;     typedef struct {    ElemType data;    int cur;  /* 游标(Cursor) ，为0时表示无指向 */} Component,StaticLinkList[MAXSIZE];/* 将一维数组space中各分量链成一个备用链表，space[0].cur为头指针，"0"表示空指针 */Status InitList(StaticLinkList space) {for(int i = 0; i < MAXSIZE - 1; i ++ )  space[i].cur = i + 1;space[MAXSIZE - 1].cur = 0; /* 目前静态链表为空，最后一个元素的cur为0 */return OK;}/* 若备用空间链表非空，则返回分配的结点下标，否则返回0 */int Malloc_SSL(StaticLinkList space) { int i = space[0].cur;           /* 当前数组第一个元素的cur存的值 */                                /* 就是要返回的第一个备用空闲的下标 */if (space[0]. cur)             space[0]. cur = space[i].cur;       /* 由于要拿出一个分量来使用了， */                                        /* 所以我们就得把它的下一个 */                                        /* 分量用来做备用 */return i;}/*  将下标为k的空闲结点回收到备用链表 */void Free_SSL(StaticLinkList space, int k) {      space[k].cur = space[0].cur;    /* 把第一个元素的cur值赋给要删除的分量cur */    space[0].cur = k;               /* 把要删除的分量下标赋值给第一个元素的cur */}/* 初始条件：静态链表L已存在。操作结果：返回L中数据元素个数 */int ListLength(StaticLinkList L){    int j = 0;    int i = L[MAXSIZE-1].cur;    while(i)    {        i = L[i].cur;        j ++;    }    return j;}/*  在L中第i个元素之前插入新的数据元素e   */Status ListInsert(StaticLinkList L, int i, ElemType e)   {      int j, k, l;       k = MAXSIZE - 1;   /* 注意k首先是最后一个元素的下标 */    if (i  ListLength(L) + 1)           return ERROR;       j = Malloc_SSL(L);   /* 获得空闲分量的下标 */    if (j)       {   L[j].data = e;   /* 将数据赋值给此分量的data */for(l = 1; l <= i - 1; l++)   /* 找到第i个元素之前的位置 */   k = L[k].cur;           L[j].cur = L[k].cur;    /* 把第i个元素之前的cur赋值给新元素的cur */L[k].cur = j;           /* 把新元素的下标赋值给第i个元素之前元素的ur */return OK;       }       return ERROR;   }/*  删除在L中第i个数据元素   */Status ListDelete(StaticLinkList L, int i)   {     int j, k;       if (i  ListLength(L))           return ERROR;       k = MAXSIZE - 1;       for (j = 1; j <= i - 1; j++)           k = L[k].cur;       j = L[k].cur;       L[k].cur = L[j].cur;       Free_SSL(L, j);       return OK;   } Status ListTraverse(StaticLinkList L){    int j = 0;    int i = L[MAXSIZE-1].cur;    while(i)    {            cout << L[i].data << " ";            i=L[i].cur;            j++;    }    cout << "\n";    return OK;}Status Reverse(StaticLinkList L){    int i = L[MAXSIZE-1].cur;    int j = 0;    int k;    while(i)    {        k = L[i].cur;        L[i].cur = j;        j = i;        i = k;    }    L[MAXSIZE-1].cur = j;}int main(){    StaticLinkList L;    Status i;    i=InitList(L);        cout << "--- Creat ---" << "\n";    cout <> n;    for(int i = 1; i > e;        ListInsert(L, i, e);    }    ListTraverse(L);    cout << "--- Reverse ---" << "\n";    Reverse(L);    ListTraverse(L);    return 0;}