本文共 3362 字，大约阅读时间需要 11 分钟。
1、数据结构是一门研究非数值计算程序设计中操作对象，以及这些对象之间的关系和操作的学科；
（数据结构是相互之间存在一种或多种特定关系的数据元素的集合。）
数据结构包括两个方面的内容：数据的逻辑结构和存储结构。同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。
2、算法是为了解决某类问题而规定的一个有限长的操作序列。
算法具有五个特性：有穷性、确定性、可行性、输入、输出。
3、时间复杂度一般是算法中最大的语句频率，一般情况下是最深层循环内的语句频度。
（1） 如果算法的执行时间不随着问题规模n的增加而增长，算法中语句的频度就是某个常数。即使这个常数再大，算法的时间复杂度都是O（1）；
（2）当有若干个循环语句时，算法的时间复杂度是由嵌套层次最深的循环语句中最内层语句的频度f（n）决定的，例：
| 1 2 3 4 | for （i=0;i<n;i++) for (j=0;j<i;j++) for (k=0;k<j;k++) x++; //其时间复杂度为O（n^3) |
（3）常见的时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O（n^2）、立方阶O（n^3）、……、指数阶O（2^n）；
4、稀疏图用 邻接表 存储节省空间，稠密图用 邻接矩阵 存储节省空间；
5、单链表的操作：
| 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 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 | #include <iostream> using namespace std; typedef struct student { int data; struct student *next; }node; //创建单链表 node *create() //不带空头节点 { int n; node *p, *c, *head=NULL; cout<< "请输入(以0结束）: " ; while (1) { cin>>n; if (n != 0) { c = (node *) malloc ( sizeof (node)); c->data = n; c->next = NULL; if (head == NULL) head = c; else p->next = c; p = c; } else break ; } return head; } //求链表长度 int length(node *head) { int len=0; node *p; p = head; while (p) { len++; p = p->next; } cout<< "链表的长度为: " <<len<<endl; return len; } //插入节点 node *insert(node *head, int dest, int num) { int d=1,flag=0; node *p0 ,*p1, *p2; p0 = (node *) malloc ( sizeof (node)); p0->data = num; p1 = head; while (p1->next != NULL) { if (dest == d) { if (head == p1) //插入在头节点前 { p0->next = p1; head = p0; } else //插入在中间节点 { p2->next = p0; p0->next = p1; } flag = 1; //表示节点已插入 break ; } p2 = p1; p1 = p1->next; d++; } if (flag == 0) { p1->next = p0; //插入在尾节点 p0->next = NULL; } cout<< "插入后的链表为：" <<endl; return head; } //链表排序 node *sort(node *head) { int n, temp; node *p; n = length(head); p = head; for ( int i=0; i<n-1; i++) { p = head; for ( int j=0; j<n-1-i; j++) { if (p->data > p->next->data) { temp = p->data; p->data = p->next->data; p->next->data = temp; } p = p->next; } } cout<< "排序后的链表为：" <<endl; return head; } //链表逆置 node *reverse(node *head) { node *p1, *p2, *p3; p1 = head; p2 = p1->next; while (p2) { p3 = p2->next; p2->next = p1; p1 = p2; p2 = p3; } head->next = NULL; head = p1; cout<< "逆置后的链表为：" <<endl; return head; } //删除节点 node *del(node *head, int num) { node *p1, *p2; p1 = head; while (num != p1->data && p1) { p2 = p1; p1 = p1->next; } if (num == p1->data) { cout<< "删除节点后的链表为：" <<endl; if (p1 == head) //若删除的为头节点 { head = p1->next; free (p1); } else //删除的为非头节点 { p2->next = p1->next; free (p1); } } else cout<<num<< "未找到相应节点。" <<endl; return head; } //打印链表 void print(node *head) { node *p; for (p = head; p; p=p->next) cout<<p->data<< " " ; cout<<endl; } int main() { node *s; s = create(); length(s); print(s); s = sort(s); print(s); s = reverse(s); print(s); s = insert(s, 3, 11); print(s); s = del(s, 2); print(s); return 0; } |
转载地址：http://wfjdl.baihongyu.com/