数据结构与算法作业一.doc

数据结构与算法作业一 本资源主要涉及到数据结构和算法的基本概念和操作，包括顺序表、单链表、栈、队列等数据结构，以及相关的算法和操作。下面是对应的知识点： 1. 顺序表：顺序表是一种线性表，元素在内存中连续存储。其长度是指数据元素的个数，而不是存储空间数减数据元素的个数或存储空间数加数据元素的个数。 2. 顺序表的存取操作：顺序表的存取操作的时间复杂度是 O(1)，这是因为在顺序表中，元素的存储地址可以通过计算得到。 3. 单链表：单链表是一种线性表，元素在内存中不连续存储，每个元素都有一个指针指向下一个元素。单链表的插入和删除操作可以通过修改指针来实现。 4. 单链表的插入操作：在单链表中，插入一个新结点可以通过修改指针来实现。例如，如果 p 所指结点不是最后结点，在 p 之后插入 s 所指结点，则执行 s->next=p;p->next=s;。 5. 单链表的删除操作：在单链表中，删除一个结点可以通过修改指针来实现。例如，如果 p 所指结点不是最后结点，删除 p 所指结点的后继结点，则执行 p->next=p->next->next;。 6. 有序单链表：有序单链表是一种单链表，元素是有序的。在插入一个新结点时，需要将其插入到合适的位置，以保持链表的有序性。时间复杂度为 O(n)。 7. 顺序表和单链表的比较：顺序表和单链表是两种不同的数据结构。顺序表的存取操作的时间复杂度是 O(1)，而单链表的存取操作的时间复杂度是 O(n)。 8. 栈：栈是一种后进先出（LIFO）的数据结构，可以用来实现递归算法。栈的入栈序列是 abcde，则栈的输出序列可能是 edcba、decba、dceab 等，但不可能是 abcde。 9. 共享栈：两个栈共享空间 s[n]，s1 栈顶 t1，栈底 0；s2 栈顶 t2,栈底 n-1，则不发生上溢的条件是 t1 < t2-1。 10. 循环队列：循环队列是一种特殊的队列，队列的头尾指针可以指向同一个元素。循环队列用数组 sequeue[m] 存放，其头尾指针分别是 front 和 rear，front 指向前一位置，则当前队列中的元素个数是 (rear-front+m)%m。 11. 循环队列的判断满条件：循环队列用数组 sequeue[m] 存放，其头尾指针分别是 front 和 rear，front 指向前一位置，则当前队列为满的条件是 front == (rear+1)%m。 12. 字符串操作：在 C 语言中，字符串可以用 char 数组或 char 指针来表示。例如，char str[5]={‘x’,‘y’,‘z’}; 或 char *ps=”xyz”; 但 char str[5]=”xyz”; 是错误的。 本资源涵盖了数据结构和算法的基本概念和操作，包括顺序表、单链表、栈、队列等数据结构，以及相关的算法和操作。