线性表的链式存储

丝性表的链式存储

线性表的链式存储

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 500010
#define INF 10000000
#define LL long long
#define eps 10E-9
#define mem(a) memset(a,0,sizeof(a))
#define w(a) while(a)
#define s(a) scanf(%d,&a)
#define ss(a,b) scanf(%d%d,&a,&b)
#define sss(a,b,c) scanf(%lld%lld%lld,&a,&b,&c)
#define MAXN 9999
#define MAXSIZE 10
#define DLEN 4
#define MAXN 9999
#define MAXSIZE 10
#define DLEN 4
using namespace std;
typedef struct node
{
int data;
struct node *next;
} Node;
void create(Node **p)
{
*p=NULL;
}
int my_insert(Node **p, int x)
{
Node *p1;
p1 = (Node *) malloc(sizeof (Node));
if (p1 == NULL)
return false;
Node *p2=*p;
while(p2 != NULL)
{
if (p2->data == x)
break;
p2= p2->next;
}
p1->data = x;
p1->next = *p;
*p = p1;
return true;
}
int my_delete(Node **head, int x)
{
Node *p=*head, *q;
if (p->data == x)//考虑头结点就是设刨除的素
{
*head = (*head)->next;
free(p);
return true;
}
else
{
q = p; p = p->next; //q指向前一个节点,p指向下一个节点
while(p != NULL)
{
if (p->data == x)
{
q->next = p->next;
free(p);
return true;
}
q = p; p = p->next;
}
}
return false;
}
int my_find(Node **head, int x)
{
Node *p=*head;
while(p != NULL)
{
if (p->data == x)
break;
p = p->next;
}
return p->data;
}
void my_clear(Node **head)
{
Node *p=*head,*q;
while (p != NULL)
{
q = p;
p = p->next;
free(q);
}
}
void my_showalldata(Node **head)
{
Node *p=*head,*q;
while (p != NULL)
{
cout<

data<< ;
p = p->next;
}
cout<
}
int main()
{
int x, n;
Node *head;
create(&head);
cout< cin>>n;
cout<>x;
my_insert(&head,x);
}
cout< my_showalldata(&head);
cout< cin>>x;
my_delete(&head,x);
my_showalldata(&head);
cout< cin>>x;
cout< // my_clear(&head);// formating
free(head);
return 0;
}

 

http://www.bkjia.com/cjjc/1032300.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1032300.htmlTechArticle线性表的链式存储 #include #include #include
#include #include #include #include #include #include #include
#define N 500010 #define INF 10000000 #define LL long long
#defin…

style=”font-family: "Microsoft YaHei"; font-size: 16px”>链式结构存储密度小,存储空间利用率低

style=”font-family: "Microsoft YaHei"; font-size: 16px”>只能顺序存储(其中指针域用来表明节点内的涉及)

style=”font-family: "Microsoft YaHei"; font-size: 16px”>插入和去操作便利

  1. 初始化线性表
    InitList(L)
  2. 销毁线性表
    DestoryList(L)
  3. 判断线性表是否也空
    ListEmpty(L)
  4. 求线性表的尺寸
    ListLength(L)
  5. 输出线性表
    DispList(L)
  6. 求线性表中某个数元素值
    GetElem(L, i, e)
  7. 按元素值查找
    LocateElem(L, e)
  8. 插入数据元素
    ListInsert(L, i, e)
  9. 除去数据元素
    ListDelete(L, i, e)

代码如下:

图片 1图片 2

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 typedef int ElemType;
  4 
  5 typedef struct LNode {
  6     ElemType data;
  7     struct LNode *next;
  8 } LinkList;
  9 
 10 /*建立单链表*/
 11 /*头插法*/
 12 void CreateListF(LinkList* &L, ElemType a[], int n) {
 13     L = (LinkList *)malloc(sizeof(LinkList));
 14     L -> next = NULL;
 15 
 16     int i;
 17     LinkList *s;
 18     for(i = 0; i < n; i++) {
 19         s = (LinkList *)malloc(sizeof(LinkList));
 20         s -> data = a[i];
 21         s -> next = L -> next;
 22         L -> next = s;
 23     }
 24 }
 25 
 26 /*尾插法*/
 27 void CreateListR(LinkList* &L, ElemType a[], int n) {
 28     L = (LinkList *)malloc(sizeof(LinkList));
 29     L -> next = NULL;
 30 
 31     LinkList *p;//指针 p 来进行操作
 32     p = L;
 33 
 34     LinkList *s;
 35     int i;
 36     for(i = 0; i < n; i++) {
 37         s = (LinkList *)malloc(sizeof(LinkList));
 38         s -> data = a[i];
 39         p -> next = s;
 40         p = s;
 41     }
 42     p -> next = NULL;
 43 }
 44 
 45 /*基本运算*/
 46 /*初始化线性表 InitList(L)*/
 47 void InitList(LinkList* &L) {
 48     L = (LinkList *)malloc(sizeof(LinkList));
 49     L -> next = NULL;
 50 }
 51 
 52 /*销毁线性表 DestoryList(L)*/
 53 void DestoryList(LinkList* &L) {
 54     LinkList *pre = L;
 55     LinkList *p = L -> next;
 56 
 57     while(p != NULL) {
 58         free(pre);
 59         pre = p;
 60         p = p -> next;
 61     }
 62 
 63     free(pre);
 64 }
 65 
 66 /*判断线性表是否为空 ListEmpty(L)*/
 67 bool ListEmpty(LinkList* L) {
 68     return L -> next == NULL;
 69 }
 70 
 71 /*求线性表的长度 ListLength(L)*/
 72 int ListLength(LinkList* L) {
 73     LinkList *p = L;
 74     int i = 0;
 75 
 76     while(p -> next != NULL) {
 77         p = p -> next;
 78         i++;
 79     }
 80 
 81     return i;
 82 }
 83 
 84 /*输出线性表 DispList(L)*/
 85 void DispList(LinkList* L) {
 86     LinkList *p = L -> next;
 87 
 88     while(p != NULL) {
 89         printf("%d ", p -> data);
 90         p = p -> next;
 91     }
 92 
 93     printf("\n");
 94 }
 95 
 96 /*求线性表中某个数据元素值 GetElem(L, i, e)*/
 97 bool GetElem(LinkList* L, int i, ElemType &e) {
 98     LinkList *p = L;
 99 
100     int k = 0;
101     while(k < i && p != NULL) {
102         k++;
103         p = p ->next;
104     }
105 
106     if (p == NULL) {
107         return false;
108     } else {
109         e = p -> data;
110         return true;
111     }
112 }
113 
114 /*按元素值查找 LocateElem(L, e)*/
115 int LocateElem_wq(LinkList* L, ElemType e) {
116     LinkList *p = L;
117 
118     int k = 0;
119     while(p != NULL) {
120         if (e == p -> data) {
121             return k;
122         }
123         p = p -> next;
124         k++;
125     }
126 
127     return 0;
128 }
129 
130 int LocateElem(LinkList* L, ElemType e) {
131     LinkList *p = L -> next;
132 
133     int k = 1;
134     while(p != NULL && e != p -> data) {
135         p = p -> next;
136         k++;
137     }
138 
139     if (p == NULL) {
140         return 0;
141     } else {
142         return k;
143     }
144 }
145 
146 /*插入数据元素 ListInsert(L, i, e)*/
147 bool ListInsert(LinkList* &L, int i, ElemType e) {
148     LinkList *p = L;
149 
150     int k = 0;
151     while(k < i - 1 && p != NULL) {//找到前驱节点
152         p = p -> next;
153         k++;
154     }
155 
156     if (p == NULL) {
157         return false;
158     } else {
159         LinkList *s;
160         s = (LinkList *)malloc(sizeof(LinkList));
161         s -> data = e;
162         s -> next = p -> next;
163         p -> next = s;
164         return true;
165     }
166 }
167 
168 /*删除数据元素 ListDelete(L, i, e)*/
169 bool ListDelete_wq(LinkList* &L, int i, ElemType &e) {
170     LinkList *pre = L;//保存第 i 个指针的前驱
171     LinkList *p = L -> next;//保存第 i 个指针的位置
172 
173     int k = 1;
174     while(k < i && p != NULL) {
175         pre = pre -> next;
176         p = p -> next;
177         k++;
178     }
179 
180     if (p == NULL) {
181         return false;
182     } else {
183         e = p ->data;
184         pre -> next = p -> next;
185         free(p);
186         return true;
187     }
188 }
189 
190 bool ListDelete(LinkList* &L, int i, ElemType &e) {
191     LinkList *pre = L;//保存第 i 个指针的前驱
192 
193     int k = 0;
194     while(k < i - 1 && pre != NULL) {
195         pre = pre -> next;
196         k++;
197     }
198 
199     if (pre == NULL) {
200         return false;
201     } else {
202         LinkList *p;
203         p = pre -> next;
204         if (p == NULL) {
205             return false;
206         }
207         e = p -> data;
208         pre -> next = p -> next;
209         free(p);
210         return true;
211     }
212 }
213 
214 int main(int argc, char const *argv[]) {
215     int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
216     LinkList *L;
217     InitList(L);
218     //CreateListR(L, a, 9);
219     CreateListF(L, a, 9);
220     DispList(L);
221     printf("length = %d\n", ListLength(L));
222     ElemType e;
223     GetElem(L, 4, e);
224     printf("fourth number = %d\n", e);
225     printf("%d is located at %d\n", e, LocateElem_wq(L, 6));
226     ListInsert(L, 2, 10);
227     DispList(L);
228     ListDelete_wq(L, 2, e);
229     DispList(L);
230     return 0;
231 }

加号求调戏

这儿是运行结果哦:

9 8 7 6 5 4 3 2 1
length = 9
fourth number = 6
6 is located at 4
9 10 8 7 6 5 4 3 2 1
9 8 7 6 5 4 3 2 1

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图