嵌入式自学第二十天（5.13）
（1）线性表顺序存储的优缺点：
优点：无需为表中逻辑关系添加额外存储空间；
可以快速随机访问元素，时间复杂度O(1)。
缺点：插入删除需要移动元素O(n）；
无法动态存储。
- 线性表链式存储。
如图，链表每个元素都包含数据和指针两部分，指针指向下一个元素，元素间不一定连续存储。
特点：，线性表链式存储结构的特点是一组任意的存储单位存储线性表的数据元素，存储单元可以是连续的，也可以不连续。可以被存储在任意内存未被占用的位置上。
所以前面的顺序表只需要存储数据元素信息就可以了。在链式结构中还需要一个元素存储下一个元素的地址。
为了表示每个数据元素，ai与其直接后继数据元素ai+1之间的逻辑关系，对ai来说，除了存储其本身的信息外，还需要存一个指示器直接后续的信息。把存储元素信息的域叫数据域，把存储直接后继位置的域叫指针域。这两部分信息组成数据元素ai的存储映像，叫结点(Node);
单链表中，c语言的描述
typedef struct person {
char name[32];
char sex;
int age;
int score;
}DATATYPE;
typedef struct node {
DATATYPE data;
struct node *next,*prev;
}LinkNode;
typedef struct list {
LinkNode *head;
int tlen;
int clen;
}LinkList;
LinkList *CreateLinkList(int len);
int InsertHeadLinkList(LinkList *list, DATATYPE data);
int ShowLinkList(LinkList *list);
LinkNode *FindLinkList(LinkList *list, char *name);
int DeleteLinkList(LinkList *list, char *name);
int ReviseLinkList(LinkList *list, char *name, DATATYPE data);
int DestroyLinkList(LinkList *list);
int InsertTailLinkList(LinkList *list, DATATYPE data);
今天学了链表创建、判断链表是否为空、头插入元素、获取链表长度、遍历链表、查找元素、删除元素，程序如下。
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 | #include "linklist.h" #include <stdio.h> #include <stdlib.h> #include <string.h> LinkList* CreateLinkList() { LinkList* ll = malloc(sizeof(LinkList)); if (NULL == ll) { fprintf(stderr, "CreateLinkList malloc"); return NULL; } ll->head = NULL; ll->clen = 0; return ll; } int IsEmptyLinkList(LinkList* ll) { return 0 == ll->clen; } int InsertHeadLinkList(LinkList* ll, DATATYPE* data) { LinkNode* newnode = malloc(sizeof(LinkNode)); if (NULL == newnode) { fprintf(stderr, "InsertHeadLinkList malloc"); return 1; } memcpy(&newnode->data, data, sizeof(DATATYPE)); newnode->next = NULL; if (IsEmptyLinkList(ll)) { ll->head = newnode; } else { newnode->next = ll->head; ll->head = newnode; } ll->clen++; return 0; } int GetSizeLinkList(LinkList* ll) { return ll->clen; } int ShowLinkList(LinkList* ll) { int len = GetSizeLinkList(ll); LinkNode* tmp = ll->head; int i = 0; for (i = 0; i < len; ++i) { printf("%s %c %d %d\n", tmp->data.name, tmp->data.sex, tmp->data.age, tmp->data.socre); tmp = tmp->next; } return 0; } DATATYPE* FindLinkList(LinkList* ll, char* name) { LinkNode* tmp = ll->head; while (tmp) { if (0 == strcmp(tmp->data.name, name)) { return &tmp->data; } tmp = tmp->next; } return NULL; } int DeleteLinkList(LinkList* ll, char* name) { LinkNode* tmp = ll->head; if (IsEmptyLinkList(ll)) { return 1; } if (0 == strcmp(tmp->data.name, name)) { ll->head = ll->head->next; free(tmp); ll->clen--; return 0; } while (tmp->next) { if (0 == strcmp(tmp->next->data.name, name)) { LinkNode* tmp2 = tmp->next; tmp->next = tmp->next->next; free(tmp2); ll->clen--; return 0; } tmp = tmp->next; } return 1; } |