c数据结构顺序表和链表相关操作

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

编译器：vs2013

内容：

  1 #include "stdafx.h"
  2 #include<stdio.h>
  3 #include<malloc.h>
  4 #include<stdlib.h>
  5 
  6 #define LINK_INIT_SIZE 100
  7 #define LISTINCREAMENT 10
  8 #define ElemType int
  9 #define OVERFLOW -2
 10 #define OK 1
 11 #define ERROR 0
 12 
 13 typedef int status;
 14 
 15 //定义顺序表，并定义一个新类型Sqlist
 16 typedef struct Sqlist{
 17     ElemType *elem;
 18     int listsize;
 19     int length;
 20 }Sqlist;
 21 
 22 //函数声明
 23 status InitList(Sqlist &L);
 24 status CreatList(Sqlist &L);
 25 status PrintfList1(Sqlist L);
 26 status PrintfList2(Sqlist L);
 27 status DeleteList(Sqlist &L, int i);
 28 status ListEmpty(Sqlist L);
 29 status ListLength(Sqlist L);
 30 status InsertList(Sqlist &L, int i, ElemType e);
 31 status DestroyList(Sqlist &L);
 32 
 33 int main()
 34 {
 35     int i, n, j;
 36     ElemType e;
 37     Sqlist L1;
 38     InitList(L1);    //顺序表初始化操作
 39 
 40     ListEmpty(L1);    //顺序表判空
 41 
 42     CreatList(L1);    //顺序表赋值操作
 43 
 44     printf("正序输出为：\n");
 45     PrintfList1(L1);    //顺序表正序输出操作
 46     printf("\n");
 47     printf("逆序输出为：\n");
 48     PrintfList2(L1);    //顺序表逆序输出操作
 49     printf("\n");
 50 
 51     ListLength(L1);    //求顺序表表长
 52 
 53     printf("请输入插入的位置i=");
 54     scanf_s("%d", &i);
 55     e = rand() % 100 + 1;
 56     InsertList(L1, i, e);    //顺序表插入操作
 57     PrintfList1(L1);
 58     printf("\n");
 59 
 60     printf("请输入删除的位置j=");
 61     scanf_s("%d", &j);
 62     DeleteList(L1, j);    //顺序表删除操作
 63     PrintfList1(L1);
 64 
 65     DestroyList(L1);    //顺序表销毁操作
 66     PrintfList1(L1);
 67     return 0;
 68 }
 69 
 70 //构建空的顺序表
 71 status InitList(Sqlist &L)
 72 {
 73     L.elem = (ElemType*)malloc(LINK_INIT_SIZE*sizeof(ElemType));
 74     if (!L.elem)
 75         exit(OVERFLOW);
 76     L.length = 0;    //将新的顺序表长度定为0
 77     L.listsize = LINK_INIT_SIZE;    //初始化顺序表大小为LINK_INIT_SIZE
 78     return OK;
 79 }
 80 
 81 //顺序表插入操作
 82 status InsertList(Sqlist &L, int i, ElemType e)
 83 {
 84     ElemType *newbase, *q, *p;
 85     if (i<1 || i>L.length + 1)
 86     {
 87         printf("未插入成功！！！\n");
 88         return ERROR;
 89     }
 90     if (L.length >= L.listsize)
 91     {
 92         newbase = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREAMENT)*sizeof(ElemType));
 93         if (!newbase)
 94             exit(OVERFLOW);
 95         L.elem = newbase;
 96         L.listsize += LISTINCREAMENT;
 97     }    //检验线性表是否满了，满了则重新增加存储空间
 98     q = &(L.elem[i - 1]);
 99     for (p = &(L.elem[L.length - 1]); p >= q; p--)
100         *(p + 1) = *p;
101     *q = e;
102     L.length++;
103     return OK;
104 }
105 
106 //顺序表输入操作
107 status CreatList(Sqlist &L)
108 {
109     ElemType i = 0, e;
110     for (i = 0; i < 10; i++)    //顺序表赋值操作
111     {
112         L.elem[i] = rand() % 100 + 1;
113         L.length++;
114     }
115     return 0;
116 }
117 
118 //顺序表正序输出操作
119 status PrintfList1(Sqlist L)
120 {
121     int i;
122     if (L.length == 0)
123     {
124         printf("该线性表为空！\n");
125         return 0;
126     }
127     for (i = 0; i < L.length; i++)
128         printf("L.elem[%d]=%d\n", i + 1, *(L.elem + i));
129 }
130 
131 //顺序表删除操作
132 status DeleteList(Sqlist &L, int i)
133 {
134     int *p, *q, e;
135     if (i<1 || i>L.length + 1)
136     {
137         printf("不存在此删除位置！！！\n");
138         return ERROR;
139     }    //检验输入的i是否在线性表所存在的范围内
140     p = &(L.elem[i - 1]);
141     e = *p;
142     q = L.elem + L.length - 1;
143     for (p++; p <= q; ++p)
144         *(p - 1) = *p;
145     L.length--;
146     printf("删除的元素为%d\n", e);
147     return 0;
148 }
149 
150 //顺序表逆序输出操作
151 status PrintfList2(Sqlist L)
152 {
153     int i;
154     if (L.length == 0)
155     {
156         printf("该线性表为空！\n");
157         return 0;
158     }
159     for (i = L.length - 1; i >= 0; i--)
160         printf("L.elem[%d]=%d\n", i + 1, *(L.elem + i));
161 }
162 
163 //求顺序表是否为空
164 status ListEmpty(Sqlist L)
165 {
166     if (L.length == 0)
167         printf("The List is Empty!!!\n");
168     else
169         printf("The List is not Empty!!!\n");
170     return 0;
171 }
172 
173 //求顺序表长度
174 status ListLength(Sqlist L)
175 {
176     printf("线性表的长度为%d\n", L.length);
177     return OK;
178 }
179 
180 status DestroyList(Sqlist &L)
181 {
182     free(&L.elem[0]);
183     L.length = 0;
184     return 0;
185 }

实验结果

链表操作

  1 #include<malloc.h>
  2 
  3 #include<stdlib.h>
  4 
  5 
  6 
  7 typedef int Elemtype;
  8 
  9 typedef int Status;
 10 
 11 
 12 
 13 typedef struct LNode{
 14 
 15     Elemtype data;
 16 
 17     struct LNode *next;
 18 
 19 }LNode, *LinkList;
 20 
 21 
 22 
 23 //函数声明
 24 
 25 Status CreatList1(LinkList &L, int n);                                   //头插法构建
 26 
 27 Status PrintfList(LinkList L);                                          //链表输出
 28 
 29 Status CreatList2(LinkList &L, int n);                                   //尾插法构建
 30 
 31 Status InverseList(LinkList &L);                                            //逆置链表
 32 
 33 
 34 
 35 int main()
 36 
 37 {
 38 
 39     LinkList L;
 40 
 41     int n, i, e;
 42 
 43 
 44 
 45     printf("请输入建立的线性表结点个数n=");
 46 
 47     scanf_s("%d", &n);
 48 
 49     CreatList1(L, n);
 50 
 51     PrintfList(L);                                                   //头插法建立链表
 52 
 53 
 54 
 55     printf("请输入建立的线性表结点个数n=");
 56 
 57     scanf_s("%d", &n);
 58 
 59     CreatList2(L, n);
 60 
 61     PrintfList(L);                                                   //尾插法建立链表
 62 
 63 
 64 
 65     InverseList(L);                                                //逆置链表
 66 
 67     PrintfList(L);
 68 
 69 }
 70 
 71 
 72 
 73 //头插法创建链表
 74 
 75 Status CreatList1(LinkList &L, int n)
 76 
 77 {
 78 
 79     int i;
 80 
 81     LinkList p;
 82 
 83     L = (LinkList)malloc(sizeof(LNode));
 84 
 85     L->next = NULL;
 86 
 87     for (i = n; i > 0; i--)
 88 
 89     {
 90 
 91         p = (LinkList)malloc(sizeof(LNode));
 92 
 93         p->data = rand() % 100 + 1;
 94 
 95         printf("头插法的第%d个数据：%d\n", i, p->data);
 96 
 97         p->next = L->next;
 98 
 99         L->next = p;
100 
101     }
102 
103     return 0;
104 
105 }
106 
107 //尾插法构建线性表
108 
109 Status CreatList2(LinkList &L, int n)
110 
111 {
112 
113     LinkList p, q;
114 
115     int i;
116 
117     L = (LinkList)malloc(sizeof(LNode));
118 
119     L->next = NULL;
120 
121     for (q = L, i = 0; i < n; i++)
122 
123     {
124 
125         p = (LinkList)malloc(sizeof(LNode));
126 
127         p->data = rand() % 100 + 1;
128 
129         printf("尾插法的第%d个数据：%d", i + 1, p->data);
130 
131         q->next = p;
132 
133         q = p;
134 
135         printf("\n");
136 
137     }
138 
139     q->next = NULL;
140 
141     return 0;
142 
143 }
144 
145 
146 
147 //输出链表
148 
149 Status PrintfList(LinkList L)
150 
151 {
152 
153     LNode *p;
154 
155     if (L->next == NULL)
156 
157         printf("The List is Empty!!!\n");
158 
159     for (p = L->next; p != NULL; p = p->next)
160 
161         printf("%3d ", p->data);
162 
163     printf("\n");
164 
165     return 0;
166 
167 }
168 
169 //逆置链表
170 
171 Status InverseList(LinkList &L)
172 
173 {
174 
175     LinkList p, q;
176 
177     for (p = L->next; p->next != NULL; p = p->next);
178 
179     for (q = L->next; q != p; q = L->next)
180 
181     {
182 
183         L->next = q->next;
184 
185         q->next = p->next;
186 
187         p->next = q;
188 
189     }
190 
191     return 0;
192 
193 }